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.
Start protecting yourself from a potential MITM better, mark the key as revoked. Hopefully distributions & OpenSSH upstream can start shipping this by default.
```
# You might need to insert this in a slightly different place
cat >>/etc/ssh/ssh_config <<EOF
Host *
RevokedHostKeys /etc/ssh/ssh_revoked_hosts
EOF