I don't think that this is the best way...
BrowserUk and I both used the core module: List::Util::shuffle;

He understood the FASTA format better than I did and that is fine given that the format of the OP's question was hard to "decode".

The main point is that is that this core shuffle() function works very well, is very fast (a core function that is implemented in 'C') and who's interface is easy to understand. I recommend using it rather than trying to "roll your own".

Oh, BTW, "Core Function" means that this is available on all Perl systems as part of the language - no "extra module installation" is required. .... Well I don't know exactly about "all", but I figure since Perl 5.6 (for more than decade).