What you want to do is actually fairly straight-forward.
For each existing key, see if there is a new name for that key.
If there is, then delete the current hash entry and create a new entry with the new name and with the current value.

Here is some simple example code.
There can be complications with this, like what happens if the new key name already exists?
Also be aware that hash keys are presented in random order.

Anyway, modify this code to meet your requirements and to take into account what I mentioned.

use strict;
use warnings;
use Data::Dump qw(pp);
$|=1;

my %hash = ( 'a' => 2,
             'b' => 3,
             'c'=> 4,
             'd' => 5);
             
my %key_map = ('a'=> 'abc',
               'd'=> 'def');
               
pp \%hash;
pp \%key_map;

############# added code #########
print "Perl size of 'hash' ", scalar(%hash),"\n";


foreach my $key (keys %hash)
{
   if (defined (my $new_key = $key_map{$key}))
   {
      print "New key for $key is $new_key\n";
      my $current_value = $hash{$key};
      delete $hash{$key};
      $hash{$new_key} = $current_value;
   } 
}
print "result of hash mods:\n";
pp \%hash;

__END__
Prints:
{ a => 2, b => 3, c => 4, d => 5 }
{ a => "abc", d => "def" }
Perl size of 'hash' 3/8
New key for d is def
New key for a is abc
result of hash mods:
{ abc => 2, b => 3, c => 4, def => 5 }
[download]

Update: It may not be obvious to you, but changing the name of a single hash key (whether longer or even shorter) could potentially cause Perl's internal representation of the hash table to be completely recalculated and reorganized. In general as a Perl'er, don't worry about it. In the internal "guts", the Perl code that deals with hashes is written in C and I must add that it is quite efficient at what it does and how it does it.

Update2: Every map statement IS a loop! It may not look that way to you, but that is what it is. Shorter source code does not necessarily equate with shorter or even more efficient executed code.

Update3: Added scalar value of a %hash to the code.