Nach etwas längerer Zeit musste ich mich wieder auf meine alt gewordene Dreambox DM800 HD PVR verbinden.
Für eine erfolgreiche Verbindung musste ich folgende Konfig in meine ~/.ssh/config mit aufnehmen.

Host dreambox
	Hostname YOUR.LOCAL.IP.ADDRESS
	User root
	KexAlgorithms +diffie-hellman-group1-sha1
	Ciphers aes128-ctr,aes192-ctr,aes256-ctr,aes128-cbc,3des-cbc

Evtl. ist dieser Beitrag auch bei anderen Fällen hilfreich beim Fehler:

no matching key exchange method found. Their offer: diffie-hellman-group1-sha1