We had bit of a problem with very slow SSH connection from couple hosts. It was weird because the same problem didn’t repeat from other hosts with very identical setup. I had similar problem home, where I ended up fixing the problem in a different way. So, here are those two fixes I found when your SSH connection takes ages (at least when using Ubuntu).
Client-side
I don’t claim to understand what GSSAPI is, but commenting out settings related to it from /etc/ssh/ssh_config and letting SSH use defaults fixed the problem when it was on the client side:
#GSSAPIAuthentication yes#GSSAPIDelegateCredentials no
Server-side
When the problem is on the server side, adding following to /etc/ssh/sshd_config and restarting SSH-daemon helps:
UseDNS no
That’s it. Wasn’t that complicated.