Connecting the SSH servers can sometimes be delayed when the client and server try to sort out if they should be using GSSAPI to authenticate. You can see if this the case by running:
ssh -vvv <yourserveraddress>
If you see mention of GSSAPI in the output and things slow down, disabling GSSAPI might help. It's unlike you'll need it if you don't know you need it, if you see what I mean :)
On the client side you can add the following to your $HOME/.ssh/config file:
Host * GSSAPIAuthentication no
To disable GSSAPI authentication on the server, as root, edit /etc/ssh/sshd_config. Change the yes on the GSSAPIAuthentication line to no. Save your changes and exit your editor, then run, as root:
# service ssh reload
If you're running Fedora, RHEL or CentOS replace ssh with sshd in the above command.