Based on your edit it sounds like the hang up is when you make the connection over SSH. If you SSH'd into the server you probably will see a similar delay.
In my experience this is usually a result of having GSSAPIAuthentication enabled, which unfortunately is enabled by default on new installations of SSH.
The most straightforward debugging and client/server fix instructions I've found are over at Coderwall.
You can disable GSSAPIAuthentication on the client or the server. I would recommend doing so on the server side, so other clients won't have this problem.