In setting up passwordless OpenSSH connections between two CentOS boxes, I was surprised to find that I could connect from the client the server, but it was really, really slow. As in, it took over a minute to connect, after which it was snappy.
Fortunately, a quick Google and I find that the OpenSSH manual has this relevant FAQ. I tried all the suggestions (couldn’t get far testing ssh-rand-helper, though, since it wasn’t apparently installed), but editing /etc/ssh/sshd_config on the server, to set
UseDNS no
was the trick. Restart sshd, and it works like a charm.