use Sort::External;

my $sortex = Sort::External->new;
while ( my ($k, $v) = each %hash) ) { # aliases, so no memory hit
    $sortex->feed($k);
}
$sortex->finish;
my $counter = 1;
while (defined($_ = $sortex->fetch)) {
   $hash{$_} = $counter++;
}