How about something very pragmatic: Use the same key you use for your webserver, which already has a valid SSL cert. Clients first connect to port 443 to get the public key and can verify the certificate. During the SSH handshake, the client then compares the host key with the previously obtained key of the certificate.