You could do one of the following.
Load the files into MP3tag.
Click on the top left column header. This arranges the files in a random order.
Now you could rename the files with:
Convert>Tag-Filename
%_counter% _ %_filename%
Or you rename them straight away with the Convert>Tag-Filename function:
$rand() _ %_filename%
or even
$num($rand(),5) _ %_filename%