As of ssh 6.8:

- ssh(1), sshd(8): Experimental host key rotation support.  Add a
  protocol extension for a server to inform a client of all its
  available host keys after authentication has completed.  The client
  may record the keys in known_hosts, allowing it to upgrade to better
  host key algorithms and a server to gracefully rotate its keys.
  The client side of this is controlled by a UpdateHostkeys config
  option (default off).

https://lwn.net/Articles/637156/

Should also work for learning new key types.