ふとあるhostにED25519のサーバ鍵がないのに気づいたので作りました．
ファイル名を指定して作るか，
$ sudo ssh-keygen -N '' -f /etc/ssh/ssh_host_ed25519_key
Generating public/private rsa key pair.
Your identification has been saved in ./ssh_host_ed25519_key.
Your public key has been saved in ./ssh_host_ed25519_key.pub.
The key fingerprint is:
f3:55:7f:02:04:92:c3:e0:4c:8c:7a:05:6a:00:28:da root@micro
The key's randomart image is:
+--[ RSA 2048]----+
|= .+oo..... |
|o. ..+o +. . |
|o.o. .o . . . |
|..E . o . |
| . S . . o|
| o . ..|
| . |
| |
| |
+-----------------+
ssh-keygen -Aで足りないものを自動生成してもらいます．-Aの場合鍵指紋が出てこないので`ssh-keygen -lfとかで確認しましょう．
$ sudo ssh-keygen -A
ssh-keygen: generating new host keys: ED25519
$ cat /etc/ssh/ssh_host_ed25519_key.pub
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAINYCcWp86jHwcb56mvdFMpCjovBH8eAa99OufTUEYycU root@micro
$ ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key
256 bf:f8:4a:5b:2d:da:72:84:e7:87:25:1b:9d:1c:56:b2 root@micro (ED25519)
規定値で有効になっていると思うけど設定ファイルにも記述してデーモンをreload．
$ grep ed25519 /etc/ssh/sshd_config
HostKey /etc/ssh/ssh_host_ed25519_key
$ sudo service ssh restart
ed25519で帰ってくるか確認．
$ ssh-keyscan -p 2222 -t ed25519 localhost
# localhost SSH-2.0-OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.6
localhost ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAINYCcWp86jHwcb56mvdFMpCjovBH8eAa99OufTUEYycU
クライアント側のknown_hostsから古いものを消して登録しなおして，
$ ssh-keygen -f ~/.ssh/known_hosts -R [192.168.1.102]:2222
$ ssh -o HostKeyAlgorithms=ssh-ed25519 micro
The authenticity of host '[192.168.1.102]:2222 ([192.168.1.102]:2222)' can't be established.
ED25519 key fingerprint is SHA256:H8TMbIG65XqBAeiST98ThJq/Ux7RHerpMGXnxVJ7EjE.
+--[ED25519 256]--+
| . . .. E. |
| . o . .=..o. |
| o o o o oB+ o |
|o = = *o+ = . |
| + o . %S+.o o |
| . o X =... |
| + B .. |
| o o o |
| . . |
+----[SHA256]-----+
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[192.168.1.102]:2222' (ED25519) to the list of known hosts.
後はDNSに登録したり……ってed25519はエラーになるみたいですね．
$ ssh-keygen -r example.org -f /etc/ssh/ssh_host_ed25519_key
export_dns_rr: unsupported algorithm and/or digest_type
ちなみにED25519はOpenSSH 6.5p1で入りました．