This was also the case with Digital Ocean's droplets on Debian for a time (they were re-imaging without re-genning keys.) It's not as uncommon as it sounds.

Userify (cloud ssh key manager) is getting a feature to force re-generation of server-side keys across an entire cluster remotely.