Existem pacotes cliente e servidor openssh atualizados em Wheezy Backports.
De acordo com o changelog , a versão backported pode trabalhar com chaves ED25519:
openssh (1:6.6p1-4~bpo70+1) wheezy-backports; urgency=low
Rebuild for wheezy-backports.
-- Colin Watson Wed, 30 Apr 2014 09:59:29 +0100
[...]
openssh (1:6.5p1-1) unstable; urgency=medium
[...]
Generate ED25519 host keys on fresh installations. Upgraders who wish to add such host keys should manually add 'HostKey /etc/ssh/ssh_host_ed25519_key' to /etc/ssh/sshd_config and run 'ssh-keygen -q -f /etc/ssh/ssh_host_ed25519_key -N "" -t ed25519'.
-- Colin Watson Mon, 10 Feb 2014 14:58:26 +0000
Para instalar pacotes wheezy-backports, siga as instruções . Em suma, você precisa adicionar a seguinte linha ao seu /etc/apt/sources.list :
deb http://http.debian.net/debian wheezy-backports main
Seria prudente ler atentamente o site de backports antes de fazer uso do repositório.