use List::Util qw(shuffle);
...
foreach my $k (shuffle keys %foo) {
...
}