Most of the answers on SO and elsewhere suggested the problem was a DNS issue. On a Debian system with a very long uptime, I saw it stalled out on talking to a dbus socket (logs shown below). Turns out, restarting dbus systemctl restart dbus
fixed the problem
15:50:20.475652 connect(4, {sa_family=AF_UNIX, sun_path="/run/dbus/system_bus_socket"}, 30) = 0 <0.000049>
15:50:20.475823 getsockopt(4, SOL_SOCKET, SO_PEERCRED, {pid=1, uid=0, gid=0}, [12]) = 0 <0.000025>
15:50:20.475981 getsockopt(4, SOL_SOCKET, SO_PEERSEC, 0x7f301f9a1340, [64]) = -1 ENOPROTOOPT (Protocol not available) <0.000024>
15:50:20.476135 getsockopt(4, SOL_SOCKET, SO_PEERGROUPS, 0x7f301f9af260, [256]) = -1 ENOPROTOOPT (Protocol not available) <0.000024>
15:50:20.476285 fstat(4, {st_mode=S_IFSOCK|0777, st_size=0, ...}) = 0 <0.000028>
15:50:20.476430 getsockopt(4, SOL_SOCKET, SO_ACCEPTCONN, [0], [4]) = 0 <0.000025>
15:50:20.476584 getsockname(4, {sa_family=AF_UNIX}, [128->2]) = 0 <0.000030>
15:50:20.476735 geteuid() = 0 <0.000023>
15:50:20.476868 sendmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="\0AUTH EXTERNAL ", iov_len=15}, {iov_base="30", iov_len=2}, {iov_base="\r\nNEGOTIATE_UNIX_FD\r\nBEGIN\r\n", iov_len=28}], msg_iovlen=3, msg_controllen=0, msg_flags=0}, MSG_DONTWAIT|MSG_NOSIGNAL) = 45 <0.000037>
15:50:20.477077 gettid() = 24520 <0.000029>
15:50:20.477234 recvmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="OK 2560c588f16861763b962af4580ec"..., iov_len=256}], msg_iovlen=1, msg_controllen=0, msg_flags=MSG_CMSG_CLOEXEC}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = 52 <0.000033>
15:50:20.477417 sendmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="l\1\0\1\0\0\0\0\1\0\0\0m\0\0\0\1\1o\0\25\0\0\0/org/fre"..., iov_len=128}], msg_iovlen=1, msg_controllen=0, msg_flags=0}, MSG_DONTWAIT|MSG_NOSIGNAL) = 128 <0.000033>
15:50:20.477592 recvmsg(4, {msg_namelen=0}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = -1 EAGAIN (Resource temporarily unavailable) <0.000032>
15:50:20.477751 ppoll([{fd=4, events=POLLIN}], 1, {tv_sec=24, tv_nsec=999662000}, NULL, 8) = 1 ([{fd=4, revents=POLLIN}], left {tv_sec=24, tv_nsec=999377054}) <0.000316>
15:50:20.478303 recvmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="l\2\1\1\16\0\0\0\1\0\0\0E\0\0\0\6\1s\0\t\0\0\0", iov_len=24}], msg_iovlen=1, msg_controllen=0, msg_flags=MSG_CMSG_CLOEXEC}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = 24 <0.000079>
15:50:20.478607 recvmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base=":1.121264\0\0\0\0\0\0\0\5\1u\0\1\0\0\0\10\1g\0\1s\0\0"..., iov_len=78}], msg_iovlen=1, msg_controllen=0, msg_flags=MSG_CMSG_CLOEXEC}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = 78 <0.000074>
15:50:20.478921 sendmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="l\1\0\1\0\0\0\0\2\0\0\0\221\0\0\0\1\1o\0\31\0\0\0/org/fre"..., iov_len=168}], msg_iovlen=1, msg_controllen=0, msg_flags=0}, MSG_DONTWAIT|MSG_NOSIGNAL) = 168 <0.000055>
15:50:20.479125 recvmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="l\4\1\1\16\0\0\0\2\0\0\0\225\0\0\0\1\1o\0\25\0\0\0", iov_len=24}], msg_iovlen=1, msg_controllen=0, msg_flags=MSG_CMSG_CLOEXEC}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = 24 <0.000036>
15:50:20.479322 recvmsg(4, {msg_name=NULL, msg_namelen=0, msg_iov=[{iov_base="/org/freedesktop/DBus\0\0\0\2\1s\0\24\0\0\0"..., iov_len=158}], msg_iovlen=1, msg_controllen=0, msg_flags=MSG_CMSG_CLOEXEC}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = 158 <0.000064>
15:50:20.479582 recvmsg(4, {msg_namelen=0}, MSG_DONTWAIT|MSG_CMSG_CLOEXEC) = -1 EAGAIN (Resource temporarily unavailable) <0.000025>
15:50:20.479754 ppoll([{fd=4, events=POLLIN}], 1, {tv_sec=24, tv_nsec=999380000}, NULL, 8) = 0 (Timeout) <25.024463>
/etc/passwd
? LDAP? Kerberos? Active Directory? NIS/YP?ssh -vvv
Adding the verbose flag to SSH commands usually helps me troubleshoot issues with login that is not immediately apparent. The first thing that you must figure out is if it is an issue with network connection (interruption // dropped packets // firewalls) or with the configuration of the machine itself. This thread is likely to go unsolved since so much time has passed, but hopefully this helps someone else coming back to this.