Strange ssh connection issue

Question

Let me start by describing the situation. (Below RP = Raspberry Pi)

1. In country A there is a RP 2 running raspbian jessie offering ssh.
2. In country B I have my lan with a laptop, a RP B running wheezy, a RP 2 running jessie, and a RP 3 also running jessie. These 4 computers are on the same lan (my home) using the same router (Time Capsule which very recently had a firmware update). So, 2 out of 4 computers can connect to the remote host, but the other 2 can not.
3. I can connect to the RP 2 in country A from my laptop as well as from RP B (which is running wheezy). I can not connect to the RP 2 in country A using either of the two remaining raspberries (the 2 and the 3 that I have in my lan, both of which are running jessie).
4. In my lan I can ssh from any computer to any other computer (which implies that my RP3 can connect to the local RP2 but not to the remote RP2).
5. The RP2 in my lan (country B) is also offering an ssh service on precisely the same port as the RP 2 in country A does; I can connect to my home lan from my cell phone (of course without using the wifi).
6. I have write permissions on all of my SD cards. In fact all of the raspberries at home have a different job to do and need to support write operations.
7. I do not have a different router to check if something with the router is wrong. However, I note that Time Capsule had its firmware updated a few days ago (to version 7.7.7). Unfortunately, I am not sure about the situation before the update.
8. The cables that I am using to connect the three RPs in my lan to my Time Capsule are these ones: http://amazon.com/Cable-Matters-160021-Snagless-Ethernet/dp/B00E5I7VJG .
9. I also started a similar thread on Raspberry Pi stack exchange (https://raspberrypi.stackexchange.com/questions/48089/can-not-ssh-on-remote-host) but most likely the issue that I am encountering is not something that necessarily falls under their spectrum.
10. As suggested at Raspberry Pi stack exchange, I did check the file sshd_config in the remote server, but I did not notice anything strange or some modification from the default files. However, I am happy to post more info and file contents if you think it is necessary for debugging.

So, the question is, do you have any idea at all as to what can possibly go wrong and these connections fail?

Note also that due to (4) I can connect from my local RP 3 to my local RP 2 and both the local RP 2 as well as the remote RP 2 (to which I can not connect to from my RP 3) are using the same software. Further, even if the log is not presented below, the output of the command ssh -vv ... connecting my local RP 3 to my local RP 2 is identical to the output that is presented below for the connection between my local RP 3 to the remote RP 2 up to the point where establishing connection (key exchange) fails.

All comments are more than welcome!

Below are various outputs that can be used for debugging the ssh connection.

FAILURES

Connecting country B, RP 3 (raspbian jessie) ---> country A, RP 2 (raspbian jessie)

or

Connecting country B, RP 2 (raspbian jessie) ---> country A, RP 2 (raspbian jessie)

the output is identically the same using diff:

$ ssh -vv -p PPPPP [email protected]
OpenSSH_6.7p1 Raspbian-5+deb8u2, OpenSSL 1.0.1k 8 Jan 2015
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxx.yyy.zzz.www [xxx.yyy.zzz.www] port PPPPP.
debug1: Connection established.
debug1: key_load_public: No such file or directory
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: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/user/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.7p1 Raspbian-5+deb8u2
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Raspbian-5+deb8u2
debug1: match: OpenSSH_6.7p1 Raspbian-5+deb8u2 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: kex_parse_kexinit: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: mac_setup: setup [email protected]
debug1: kex: server->client aes128-ctr [email protected] none
debug2: mac_setup: setup [email protected]
debug1: kex: client->server aes128-ctr [email protected] none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
Connection closed by xxx.yyy.zzz.www
$

SUCCESSES

Country B, RP B (raspbian wheezy) ---> Country A, RP 2 (raspbian jessie):

$ ssh -vv -p PPPPP [email protected]
OpenSSH_6.0p1 Debian-4+deb7u4, OpenSSL 1.0.1e 11 Feb 2013
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxx.yyy.zzz.www [xxx.yyy.zzz.www] port PPPPP.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type -1
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: identity file /home/user/.ssh/id_dsa type -1
debug1: identity file /home/user/.ssh/id_dsa-cert type -1
debug1: identity file /home/user/.ssh/id_ecdsa type -1
debug1: identity file /home/user/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Raspbian-5+deb8u2
debug1: match: OpenSSH_6.7p1 Raspbian-5+deb8u2 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.0p1 Debian-4+deb7u4
debug2: fd 3 setting O_NONBLOCK
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,[email protected],[email protected],[email protected],[email protected],ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,[email protected],hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,[email protected],hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: kex_parse_kexinit: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: mac_setup: found hmac-sha1
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug2: mac_setup: found hmac-sha1
debug1: kex: client->server aes128-ctr hmac-sha1 none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 61:58:bc:cd:17:4d:4f:cf:b0:90:f3:69:52:aa:1e:a9
debug1: Host '[xxx.yyy.zzz.www]:PPPPP' is known and matches the ECDSA host key.
debug1: Found key in /home/user/.ssh/known_hosts:5
debug1: ssh_ecdsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /home/user/.ssh/id_rsa ((nil))
debug2: key: /home/user/.ssh/id_dsa ((nil))
debug2: key: /home/user/.ssh/id_ecdsa ((nil))
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Trying private key: /home/user/.ssh/id_rsa
debug1: Trying private key: /home/user/.ssh/id_dsa
debug1: Trying private key: /home/user/.ssh/id_ecdsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password
[email protected]'s password: 
debug2: we sent a password packet, wait for reply
debug1: Authentication succeeded (password).
Authenticated to xxx.yyy.zzz.www ([xxx.yyy.zzz.www]:PPPPP).
debug1: channel 0: new [client-session]
debug2: channel 0: send open
debug1: Requesting [email protected]
debug1: Entering interactive session.
debug2: callback start
debug2: client_session2_setup: id 0
debug2: fd 3 setting TCP_NODELAY
debug2: channel 0: request pty-req confirm 1
debug1: Sending environment.
debug1: Sending env LANG = en_GB.UTF-8
debug2: channel 0: request env confirm 0
debug2: channel 0: request shell confirm 1
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug2: channel_input_status_confirm: type 99 id 0
debug2: PTY allocation request accepted on channel 0
debug2: channel 0: rcvd adjust 2097152
debug2: channel_input_status_confirm: type 99 id 0
debug2: shell request accepted on channel 0

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.
Last login: ??? May ?? ??:??:?? 2016 from aaa.bbb.ccc.ddd
$

Country B, Macbook Pro (OS X 10.11.5) ---> Country A, RP 2 (raspbian jessie):

$ ssh -vv -p PPPPP [email protected]
OpenSSH_6.9p1, LibreSSL 2.1.8
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 20: Applying options for *
debug1: /etc/ssh/ssh_config line 102: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxx.yyy.zzz.www [xxx.yyy.zzz.www] port PPPPP.
debug1: Connection established.
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_rsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_rsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/user/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.9
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Raspbian-5+deb8u2
debug1: match: OpenSSH_6.7p1 Raspbian-5+deb8u2 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to xxx.yyy.zzz.www:PPPPP as 'user'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,[email protected],[email protected],[email protected],[email protected],[email protected],ssh-ed25519,ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: kex_parse_kexinit: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug1: kex: server->client [email protected] <implicit> none
debug1: kex: client->server [email protected] <implicit> none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:6eXFngBnUIqMlCL6WoR/miDXvVSQHjko8iPKScNMJpA
debug1: Host '[xxx.yyy.zzz.www]:PPPPP' is known and matches the ECDSA host key.
debug1: Found key in /Users/user/.ssh/known_hosts:29
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /Users/user/.ssh/id_rsa (0x0),
debug2: key: /Users/user/.ssh/id_dsa (0x0),
debug2: key: /Users/user/.ssh/id_ecdsa (0x0),
debug2: key: /Users/user/.ssh/id_ed25519 (0x0),
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Trying private key: /Users/user/.ssh/id_rsa
debug1: Trying private key: /Users/user/.ssh/id_dsa
debug1: Trying private key: /Users/user/.ssh/id_ecdsa
debug1: Trying private key: /Users/user/.ssh/id_ed25519
debug2: we did not send a packet, disable method
debug1: Next authentication method: password
[email protected]'s password: 
debug2: we sent a password packet, wait for reply
debug1: Authentication succeeded (password).
Authenticated to xxx.yyy.zzz.www ([xxx.yyy.zzz.www]:PPPPP).
debug1: channel 0: new [client-session]
debug2: channel 0: send open
debug1: Requesting [email protected]
debug1: Entering interactive session.
debug2: callback start
debug2: fd 3 setting TCP_NODELAY
debug2: client_session2_setup: id 0
debug2: channel 0: request pty-req confirm 1
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8
debug2: channel 0: request env confirm 0
debug2: channel 0: request shell confirm 1
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug2: channel_input_status_confirm: type 99 id 0
debug2: PTY allocation request accepted on channel 0
debug2: channel 0: rcvd adjust 2097152
debug2: channel_input_status_confirm: type 99 id 0
debug2: shell request accepted on channel 0

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.
Last login: ??? May ?? ??:??:?? 2016 from aaa.bbb.ccc.ddd
$ 

Answer 1

Breaking connection during key exchange is usually caused by some broken router on the way, unable to handle the MTU correctly and dropping "large enough" packets.

It is most probably MTU issue as described in the article The mysterious case of broken SSH client (“connection reset by peer”. Trying to set up some lower value than ethernet default (1500) might solve the problems:

• Debian/Ubuntu: in /etc/network/interfaces change/add line

  mtu 1200
  

  and restart network: /etc/init.d/networking restart

• RHEL/CentOS/Fedora: /etc/sysconfig/network-scripts/ifcfg-eth0 (based on your actual interface)

  MTU="1200"
  

  and restart network manager: service network restart

Also setting shorter list of Ciphers, KexAlgorithms or MACs on both server and client might be a trigger.