Acabei de ter este problema. Foi o que fiz para corrigir isso:
Baixe a versão mais recente do PuTTY (eu estava usando 0,62 em vez de 0,63) Na configuração PuTTY, vá para Conexão- > SSH e mova "Blowfish" para o topo da lista em "Política de seleção de criptografia de criptografia".