for my $k1 = (sort keys %$rHash) #outer key, this works

No it doesn't. First, it doesn't compile. Second, you stated that $recNo is numeric and you are not sorting numeric. This should work (untested!):

foreach my $k1 ( sort { $a <=> $b } keys %hash ) {
    foreach my $k2 ( sort {$a <=> $b } keys %{$hash{$k1}} ) {
        #do what you want, e.g. print $hash{$k1}{$k2}{first}
    }
}
[download]

See perldoc sort for more information.