Não há necessidade de usar putty para isso. Você pode usar o terminal.
sudo apt-get install openssh-client
ssh username@serveraddress
Não tenho certeza se isso resolve o problema, mas você pode tentar. Isso também lida com suas chaves públicas e deve fornecer sugestões sobre o que fazer se houver um erro-chave.