Putty works but ssh from terminal fails after SSH2_MSG_KEXINIT

Question

I have had problems connecting with ssh through the terminal to different machines around my workplace and my home.

The three last lines is (if I run ssh with -vvv):

debug3: load_hostkeys: loaded 0 keys
debug1: SSH2_MSG_KEXINIT sent
Read from socket failed: Connection reset by peer

There is no problem with the network, because putty works perfectly with the exact same server. Also, if I sit down with my colleagues machine (also ubuntu, same version as mine, 11.04), it works like a charm from the terminal.

I have tried to delete my .ssh . So I guess something else is wrong, anything I can do to uninstall and reinstall or delete to reset this?

EDIT: I found a duplicate: https://serverfault.com/questions/265244/ssh-client-problem-connection-reset-by-peer

Answer 1

My own question was answered on the duplicate question on serverfault (first answer). I added:

HostKeyAlgorithms ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-rsa,ssh-dss 

to ~/.ssh/config

Answer 2

The behavior of the ssh-client is also influenced by /etc/ssh/ssh_config. Maybe you edited it somehow?