I'm actually using IP addresses directly. I have script files that I use to connect to SSH servers, so that I can tab-complete the names, and so I don't forget to change the username when I'm connecting to the uni machines. Besides, I have their names in /etc/hosts so they shouldn't try to resolve beyond the LAN.
99.99999% of the time this is a DNS issue. But the delay is not on your end, it's on the server end. The delay is almost certainly the server trying to do a reverse-lookup on your IP address to find out your hostname.
I don't believe sshd uses hosts when doing a reverse lookup. Have you tried setting UseDNS to off? Default is to on... Remember to kill -HUP the process (or maybe stop/start it in Sharing) after making the config change.
Do ssh -v -v -v [hostname] to see where it's hanging. Mine hangs on debug3: Trying to reverse map address ww.xx.yy.zz. for about 30 seconds then continues with the messages debug1: Miscellaneous failure No credentials cache found
debug1: Miscellaneous failure No credentials cache found.
...but I don't have time to resolve it just now :(
Nope, that made absolutely no difference. (I did it on both client and server just to be sure I wasn't misunderstanding you).
Also, it doesn't solve my problems connecting to the uni servers. If I do ssh -v -v -v raven.csd.abdn.ac.uk from my iBook, it stalls on debug3: Trying to reverse map address 188.8.131.52. If I do the exact same thing on my Gentoo server (with all the same network settings), It doesn't try to reverse-map.