If you are using the dated SSH Secure Shell Client 3.2.9, you may have issue connect to the more updated OpenSSH Server.
If you cannot change the client (which is recommended), you will have to update the OpenSSH Server on Linux. Add this in
# vim /etc/ssh/sshd_config
# Ciphers Ciphers aes128-cbc,aes192-cbc,aes256-cbc,blowfish-cbc,arcfour KexAlgorithms diffie-hellman-group1-sha1
*If you are using Centrify-OpenSSH, you have to modify /etc/centrifydc/ssh/sshd_config and do the same