Gere um par de chaves e armazene a chave pública no servidor, conforme sugerido pela @Zoredache. Digite uma senha para proteger a chave privada e clique em Save private key e salve a chave. no seu perfil de usuário. Remova a permissão para todos, exceto você, do arquivo de chave.
Para poder autenticar com sua chave privada, você precisa disponibilizá-lo para o PuTTY. Ou carregue com Pageant ou insira-o no diálogo de configuração do PuTTY em Connection > SSH > Auth (clique em Browse... e escolha o arquivo que acabou de salvar).
Na mesma caixa de diálogo, categoria Session insira o nome do host ou endereço IP do host ao qual você deseja se conectar no respectivo campo. Mude para a subcategoria Logging e clique em All session output e, em seguida, clique em Open .
Quando a janela do terminal for aberta, clique com o botão direito do mouse na barra de título e selecione Event Log . Este log do lado do cliente complementa auth.log no lado do servidor e deve ajudá-lo a descobrir o que está acontecendo.