# In your code you are sorting on the length of the replacement strings
# instead of the search strings.  I'm guessing that's not what you want,
# so I switched it to sort on the search patterns.
my @keys_ordered = sort { length $b <=> length $a } keys %$table_ref;

# Join your strings into one big long RE
my $re_string = join '|', map( qr/\Q$_\E/, @keys_ordered );
my $re = qr/($re_string)/;

my $replacecount = 0;
while ( my $line = <INFILE> ) {
    # The inner loop is gone
    $replacecount += ( $line =~ s/$re/$table_ref->{$1}/g );
    print OUTFILE $line;
}    
print "Made $replacecount replacements.\n";