1. IIRC UpdateHostKeys does not remove the old key, so it would still be there, lurking (I haven't checked the code).

2. It was only added in OpenSSH 6.8, so it missed Ubuntu 14.04 release, and only really turned up in 16.04 LTS that way, plenty of old systems it wouldn't work on.

As other posters noted, a bad actor could rotate the key to their chosen keys just as easily as GitHub could cause the rotation.