tl;dr Fix the DNS resolver configuration on the server. (a workaround is to turn off reverse lookups in SSHD but it is better to fix what is broken)
Original answer
Anyone have any ideas why this might be?
Not really but here's an anecdote that might help:
In the past, with a different protocol, when a connection takes unusually long to be established I have found that one cause is DNS timeouts as the server tries to lookup the name of an IP-address so it can record the client name in it's logs. If your client IP-address isn't properly known to the local DNS service and DNS isn't properly configured then the server can wait a long time for DNS to time-out.
The way to look for this sort of effect is to run network sniffers, initially at the client but also at the server, then you may be able to see some network traffic related to the connection, that takes a long time to get a response, or which gets no response (you may see retries)
tcpdump and wireshark are good.
Update 1
At the client with the delay in connecting
At the server
- look up the name of the client
- check in
/etc/resolv.conf for the address of the first DNS nameserver
- type
dig -x 192.168.n.m @nameserver or host 192.168.n.m server where 192.168.n.m is replaced by the actual IP-address of the client and nameserver is the IP-address of the nameserver.
- repeat for other nameservers listed in
/etc/resolv.conf
the server should get a response in milliseconds. With a broken DNS config it will take several seconds to time out.
good config
# time host 192.168.3.4
Host 4.3.168.192.in-addr.arpa. not found: 3(NXDOMAIN)
real 0m0.130s
user 0m0.000s
sys 0m0.020s
bad config
# echo nameserver 1.2.3.4 > /etc/resolv.conf
# time host 192.168.3.4
;; connection timed out; no servers could be reached
real 0m10.010s
user 0m0.000s
sys 0m0.010s
Note the 10 second delay. That means any SSH service that wants to have client names in it's logs will take 10s to set up a SSH connection.
Update 2
It turns out this Q is (probably) an exact duplicate of Why does the "password" prompt take forever when I SSH into my Ubuntu 9.05 server?
Solution
Fix the DNS resolver configuration on the server.