Delays when ssh'ing in are almost always DNS related. To diagnose this, ssh into the machine from a known good box (that doesn't see the delays elsewhere) with the command line "ssh -vv username@hostname" and see where the delay is. It's likely that the server that is giving you the delay is trying to reverse lookup the IP of the machine you are sshing from and timing out (hence the delay).

To fix, edit your ssh config ("/etc/ssh/sshd_config") and add a "UseDNS no" line (or change the existing one to this).

Then restart your sshd via "sudo /etc/init.d/ssh restart".

Hope that helps.