I’ve had several occasions in the past where the initial ssh connection has been slow to setup. Once you’re logged in then the connection is fast. I’ve always looked to dns resolving issues for these type or problems. Either disabling UseDNS in the sshd.conf file or adding the line GSSAPIAuthentication no to your ~/.ssh/config file.
[Edit]Excellent article here explaining the issue http://injustfiveminutes.com/2013/03/13/fixing-ssh-login-long-delay/