The question I'd be asking is why you're slurping the whole file in at one time and wanting to do one substitution. It's neat and all, but don't make things too complicated if you don't have to. While the following sounds inefficient, this actually works quite well, in practice:

while (<IN_FILE>) {
    foreach my $key (keys %substitute_hash) {
        s/$key/$substitute_hash{$key}/g;
    }
}
[download]

Now, obviously, you'll need to assign the sub'ed into string to something if you want to save it and this will also overwrite previous substitutions. That may or may not be a factor.

Now, if you want to do this real-time, you'll want to do it as above. But, I have a script that reads through some 100,000 lines of code in ~1450 files doing a given match and it runs in 10-30 seconds. (This is a compilation script, in case you're wondering.) I also have another script that does a number of matches and cross-correlations on those same files and it runs in about 2 minutes. Unless you really need to get faster than that, KISS.