SSH random connect timeout

I'm having a strange issue trying to connect to a server through SSH. More than 80% of times I get a connection timeout, but sometimes manages to connect.

I'm behind a router so everyone in the office has the same external IP, but somehow I get lots of connection timeouts, but one of the coworkers, who is running Windows + Putty, does not have the issue.

Example:

user@user-HP-Pavilion-Gaming-Notebook ~ $ date; ssh -vvv [email protected]

Wed Mar 15 12:58:53 CET 2017
OpenSSH_7.2p2 Ubuntu-4ubuntu2.1, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: resolving "srv.domain.com" port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to srv.domain.com [122.55.66.77] port 22.
debug1: connect to address 122.55.66.77 port 22: Connection timed out
ssh: connect to host srv.domain.com port 22: Connection timed out





user@user-HP-Pavilion-Gaming-Notebook ~ $ date; ssh -vvv [email protected]

Wed Mar 15 12:58:59 CET 2017
OpenSSH_7.2p2 Ubuntu-4ubuntu2.1, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: resolving "srv.domain.com" port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to srv.domain.com [122.55.66.77] port 22.
debug1: connect to address 122.55.66.77 port 22: Connection timed out
ssh: connect to host srv.domain.com port 22: Connection timed out



user@user-HP-Pavilion-Gaming-Notebook ~ $ date; ssh -vvv [email protected]

Wed Mar 15 12:59:03 CET 2017
OpenSSH_7.2p2 Ubuntu-4ubuntu2.1, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: resolving "srv.domain.com" port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to srv.domain.com [122.55.66.77] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.2p2 Ubuntu-4ubuntu2.1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Debian-5+deb8u3
debug1: match: OpenSSH_6.7p1 Debian-5+deb8u3 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to srv.domain.com:22 as 'root'
debug3: hostkeys_foreach: reading file "/home/user/.ssh/known_hosts"
debug3: record_hostkey: found key type ECDSA in file /home/user/.ssh/known_hosts:12
debug3: load_hostkeys: loaded 1 keys from srv.domain.com
debug3: order_hostkeyalgs: prefer hostkeyalgs: [email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521
debug3: send packet: type 20
debug1: SSH2_MSG_KEXINIT sent

I also tried to check if there is some info about the issue in /var/log/auth.log, but I cannot see anything when I try to connect and I'm getting the timeout.

The server responds well to ping, but I also tried to connect through telnet to the port 22, and same timeout.

Any ideas?

I'm running Linux Mint, and the server is under Debian Jessie.


I was facing the exact issue.

But it turns out my RSA key was the culprit. I was using RSA with a key length of 4096 bit. After changing my private key to ed25519, I did not face the problem again.