Your question give me the opportunity to answer using the Knime workbench and the 'fasta node' I've recently described: http://plindenbaum.blogspot.fr/2015/02/automatic-code-generation-for-knime.html

1. Download knime from https://www.knime.org/downloads/overview
2. Download my fasta extension from http://cardioserve.nantes.inserm.fr/~lindenb/knime/fasta/ and put the *.jar file in the plugin directory of knime : something like .../knime_2.11.1/plugins/com.github.lindenb.xsltsandbox_2015.02.18.jar
3. Open knime
4. Create a node to read the fasta, a node reading a file with two columns (old-name,new-name). Join both file, save the result as fasta. I've uploaded a full example on myexperiment.org: http://www.myexperiment.org/workflows/4643.html?version=1

If you are already using Galaxy you could ask your Galaxy Admin to install this tool of mine:

https://github.com/peterjc/pico_galaxy/tree/master/tools/seq_rename

http://toolshed.g2.bx.psu.edu/view/peterjc/seq_rename

This takes a sequence file (FASTA, FASTQ or even SFF format) and a name mapping table, just a tabular file where you have the old names in one column, and the new names in another column. Of course, you may still have to do some work to get the renaming information into this format...

Large data! I think you eventually have to use linux. You may have to write a a script if the fastafile is bigger to change header names.

Following command should work in linux for your case.

sed -i -e 's/>A/>K/;s/>B/>L/;s/>C/>M/;s/>D/>N/;s/>E/>O/;s/>F/>P/;s/>G/>Q/;s/>H/>R/;s/>I/>S/;s/>J/>T/' filename.fasta