A delay of several seconds every time when connecting via ssh is usually due to the remote host trying to look up your IP address and timing out. Change the remote host's sshd_config file to include the line "UseDNS no" and connecting will be much quicker from then on.

You may be experiencing the GSSAPIAuthentication delay.

The -v flag will help identify where the connection is being delayed.

ssh -v [user@]hostname [command]

Try connecting with the option disabled.

ssh -o GSSAPIAuthentication=no [user@]hostname [command]

You can globally disable GSSAPIAuthentication in ssh config:

echo 'GSSAPIAuthentication=no' >> ~/.ssh/config

Thats probably because the server is trying to lookup the client on DNS: http://www.turnkeylinux.org/blog/slow-ssh

Initiating an SSH connection takes 300ms on my LAN.

If it's taking you several seconds then you probably have a reverse DNS problem. (By default, the SSH server looks up the reverse DNS of the client when it connects.)

It shouldn't take much longer than an HTTPS connection, could be something with your server configuration or latency?

Slow SSH session is usually a DNS issue.

There are many possible causes, but the biggest one is that openssl is notoriously slow at the handshake process. Changing the cipher, playing with DNS, turning off unnecessary features and tuning the order of operations can speed up the process. Otherwise, try a different ssh daemon that doesn't use openssl.

TLS also takes some time to initiate a session, but that hasn't turned anyone off SPDY, since it supports concurrency from then onwards. :-)

It could also be your shell on the remote host taking it's time. Some distros have gotten a bit bloated.