SSH Secure Shell(CLIENTE) dando erro ao conectar com o Debian 8 [RESOLVIDO]

Boas!!!
Galera, tô com um probleminha, seguinte tenho um parceiro que sempre me pede servidores Debian, este Cliente desenvolve software para diversas empresas e vem utilizando o Cliente SSH Secure Shell, que até agora não tinha me dado nenhum problema, eis que chegou e ficou estável o Debian 8, o OpenSSH deste veio com uma versão mais nova, quando tento conectar por este cliente, ele me dá um erro de "Algorithm negotiation failed", gostaria de saber como posso resolver este problema, gostaria de mexer somente em configurações do SSH secure e não no servidor, se possível, se alguém puder me ajudar, desde já fico muito grato!

Amigo isso ocorre quando você tenta se comunicar ao servidor ? Com qual usuário você esta tentando ?

Bom, eu uso um usuário administrativo, com poder de root, deixe te explicar algumas coisas, tenho diversos debian 6 e 7 rodando ate hj e nunca aconteceu, tentei pelo servidor debian 7 e funcionou, direto pelo bash, e consegui conectar. o meu maior problema é que como este cliente/parceiro administra muitos servidores linux, ele não quer sair deste cliente(SSH secure Shell). será que tem alguma coisa que posso configurar neste cliente pra ele funcionar?

Bem, eu notei que o Debian 8 vem configurado para não aceitar o login com root via ssh. Quando isso ocorre eu configuro o arquivo sshd_config da seguinte forma: Altero a linha PermitRootLogin without-password para PermitRootLogin yes.

O arquivo fica em /etc/ssh/

Isso eu já fiz, mas mesmo assim dá o mesmo erro, pelo linux de outra maquina rola, acredito que tenha problemas com a chave que o ssh cria durante a instalação, pois até o debian 7 o tamanho da chave do servidor era 768 e agora é 1024, mas não sei como configurar esta para ser compatível com o cliente ssh ou o contrário. até pensei em fazer um downgrade do Openssh, mas não sei como fazer isso, pois este pacote já vem pré configurado no repositório de segurança, e não sei se assim deixaria o servidor mais inseguro. eu gostaria, se possível mexer somente no cliente, pois acredito que daki pra sempre será uma constante.

Prezados,

Conseguiram resolver este problema? Estou tentando conectar via SSH Secure Shell ao servidor Ubuntu 16.04 e é retornado o erro "Algorithm negotiation failed".

Via Putty consigo logar no servidor.

Desde já Obrigado!

Cavalheiros,

Para mim se resolveu adicionando esta linha:

# vim /etc/ssh/sshd_config 

# Ciphers

Ciphers aes128-cbc,aes192-cbc,aes256-cbc,blowfish-cbc,arcfour

KexAlgorithms diffie-hellman-group1-sha1 

Fonte:
https://linuxcluster.wordpress.com/2016/08/15/algorithm-negotiation-failed-for-ssh-secure-shell-clie...