• Give an example of your data; Data::Dumper is your friend
• Devel::Size is your friend also

In general: Your problem might not be the keys, but the values of your hash.

#!/usr/bin/perl

use warnings;
use strict;

use Devel::Size qw(size);

my %hash = ();

for my $key (1..27000) {
    $hash{"blahblahblahblah$key"} = 1;
}

print size(\%hash);
[download]

The keys are really not small here and they also contain a hell of redundant data. But size for the hash speaks of 1736142 bytes. It also has 27.000 entries like yours. I think your optimizing on the wrong part of your data structure.