SSH: No supported key exchange algorithms [preauth]

I’ve recently installed Solaris 11.4 on a VM and, as soon as I tried to log in remotely using SSH, my connection was refused straight away. First of all, I checked if the service was enabled:

$ svcs ssh
STATE          STIME    FMRI
online         13:23:15 svc:/network/ssh:default

I checked SSH directory under /etc and something was definitely not quite right with the auto-generated keys:

-rw-------   1 root     root         0 Jan  4 13:23 ssh_host_ed25519_key
-rw-r--r--   1 root     root         0 Jan  4 13:23
-rw-------   1 root     root         0 Jan  4 13:23 ssh_host_rsa_key
-rw-r--r--   1 root     root         0 Jan  4 13:23

The keys were there… but truncated to zero.

Something, somewhere went wrong during the key generation (usually when OpenSSH is run for the first time) so I deleted the keys and restarted the service:

# svcadm restart ssh

The keys were re-generated and I was able to log in.