This has happened to me in the past when you connect to a SSH server and the initial connection is really slow, it can be really annoying. After trying a few different things and after looking at debug information I found that the following solution worked for me.

Edit /etc/ssh/ssh_config on the local machine and make sure the option “GSSAPIAuthentication” is set to no.

Hopefully that will help a few people!