Algorithm negotiation fail in Jenkins
I figured it out, I am using Ubuntu 15.04 as remote host which uses ssh version 6.7 and this version disabled most of the encryption algorithm by default. And I needed to add this line:
KexAlgorithms diffie-hellman-group1-sha1,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1NOT to the ssh_config, BUT to sshd_config.