Have a look at seq-shuf, it's a simple perl script that uses bash sed and shuffle. It is reasonable fast, basically handles files of arbitrary size and also reads from stdin.

# FASTA
cat A.fa [B.fa ..] | seq-shuf > AB-shuf.fa
# FASTQ
cat A.fq [B.fq ..] | seq-shuf > AB-shuf.fq
# FASTQ paired end
interleave A_[12].fq .. | seq-shuf --pe | interleaved-split 1> A-shuf_1.fq 2> A-shuf_2.fq

EDIT:

| file   | desc                                        |
|--------+---------------------------------------------|
| sr.fq  | short reads of 100 bp length in FASTQ       |
| gen.fa | generic FASTA sequences, 100-10k bp, N50 2k |
| asm.fa | long FASTA sequences, 100-300k, N50 100k    |

|        |          |   200 MB            |     2 GB            | 200GB               |
|        |          | time [s] | mem [GB] | time [s] | mem [GB] | time [s] | mem [GB] |
|--------+----------+----------+----------+----------+----------+----------+----------|
| sr.fq  | seq-shuf |      1.5 |      0.1 |       21 |      0.1 |    2199  | 0.1      |
|        | bbmap    |        3 |      0.6 |       40 |      4.2 | -        |          |
| gen.fa | seq-shuf |        1 |      0.1 |        9 |      0.1 |    1360  | 0.1      |
|        | bbmap    |      1.5 |      0.4 |       13 |      4.0 | -        |          |
| asm.fa | seq-shuf |      0.3 |      0.1 |        5 |      0.1 |    876   | 0.1      |
|        | bbmap    |      1.3 |      0.4 |       14 |      3.8 | -        |          |

The BBMap package has a pair of programs which will do this:

shuffle.sh in=file.fa out=shuffled.fa
reformat.sh in=shuffled.fa out=topTen.fa reads=10

...which gives you the first 10 sequences in the randomized file. But shuffle loads the entire file into memory, so it's easier to subsample like this:

reformat.sh in=file.fa out=sampled.fa samplereadstarget=10

...which gives you 10 random sequences, or

reformat.sh in=file.fa out=sampled.fa samplerate=0.01

...which gives you 1% of the sequences at random. Neither of those load the file into memory. Reformat also has a samplebasestarget flag if you want a specific number of bases rather than number of sequences.

Because GNU shuf chokes with memory exhausted errors on large inputs, I wrote a tool to handle shuffling or sampling of very large generic text files called sample.

This tool can be used to shuffle FASTA files, as well as BED, FASTQ, and other text-based genomic data sets.

Unlike shuf and alternatives, sample does not load the entire file into memory, but instead finds the positions where lines or groups of lines start, and samples from those. The memory usage is 8 bytes (per offset) times the number of headers, which for an 8 Gb input will be very very low compared with other reservoir sampling approaches - and no separate index file required.

More information about sample is available on Github.

For example, to generate a uniformly, randomly shuffled sample (without replacement) of size N from a two-lined FASTA file (where header and sequence alternate on separate lines) called input.fa, you can run the following command:

$ sample --sample-size=N --lines-per-offset=2 input.fa > sample.fa

Replace N with the desired number of FASTA sequences.

Run sample --help for more options (sampling with replacement, etc.).

pyfaidx is a good fit here:

The sequence identifiers and offsets are read from an index file, and the Fasta object does name-based lookups. That means you can get optimal performance (never reading more than a line of sequence in memory) while still using Python functions that operate on dictionary-like objects.