You only care if the keys are the same, correct? So why check every key of one hash against every key of the other? Instead, get the list of keys from one, and check to see if they are all in the other. Then check the values for each hash for the same keys.

Example: (Untested)

my @found_keys = grep { exists($hash_b{$_}) } keys %hash_a;
my @matched_keys = grep { $hash_a{$_} eq $hash_b{$_} } @found_keys;

if ( @found_keys == keys %hash_a ) {
    # All keys in %hash_a were found.
}

if ( @found_keys == keys %hash_b ) {
    # All keys in %hash_b were found.
}

if ( @found_keys == @matched_keys ) {
    # All keys matched values.
}
[download]

Update: It got pointed out to me that if found_keys and @matched_keys are both empty, the last case would return true. Which is technically correct - all found keys matched values, since none were found - but may not be what you want. Checking the length of one of them as well might help in that case.