Your post could be served greatly by improved formatting. Specifically, by wrapping your code, input and output in <code> tags, your code and samples wouldn't get mangled, and helpful monks like myself could help you with less effort. See Markup in the Monastery.

Rather than doing your reformatting after the fact, I would make it so that your array of lines (@file) is ready after input. I would accomplish this by slurping the file and then manually splitting where you want breaks. Perhaps something like:

my @file = do {
   local $/;
   $_ = <FILE>;
   split /(?=>)/;
};
[download]

As well, rather than randomly splicing, I would think you'd get similar performance and better clarity by using the shuffle method from (the core module) List::Util. Then you could just print them off in the new order, or shift/pop off values as you needed them.

Be aware that these approaches are likely sub-optimal for very large files.