OpenSSH 7.4p1にて検証した手順です。
※「{{ }}」にて囲まれている部分は変数を表します(Jinja2などのテンプレートエンジンでもレンダリング可能なようにしてあります)。
設定を変更する部分のみ記載。
$ sudo vi /etc/ssh/sshd_config
==========
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key
PublicAuthentication yes
AuthorizedKeysFile .ssh/authorized_keys
PasswordAuthentication no
AllowTCPForwarding yes
TCPKeepAlive yes
UsePAM no
==========
$ ssh-keygen -t ed25519 -C "{{ Comment }}"