Invalid host key on the Ubuntu 16.04 image in our repo

Error when connecting from the command line:

Unable to negotiate with 108.60.199.107: no matching host key type found. Their offer: ssh-dss

And, when rechecking status in Cloudmin:

No SSH - Invalid host key

The image in our repo for Ubuntu 16.04 has a deprecated host key type, which leads to modern Cloudmin hosts and recent openssh versions from being able to communicate with it via ssh. A new host key using a more modern algorithm than dss would be the solution to that. Here's a stackoverflow discussion of a similar problem: http://stackoverflow.com/questions/34208495/unable-to-negotiate-with-xx-...

I'm surprised Ubuntu 16.04 would default to generating a host key with an old protocol...But, I guess it does, as we don't have this problem in other images for other distros, so i guess it isn't something Cloudmin is generating, or is it, and Ubuntu just has bad defaults?