For what it is worth, this seems to be when/why the host keys changed:
root@trac:~# grep -B1 \ google-compute-engine$ /var/log/apt/history.log
Start-Date: 2022-08-28 11:13:16
Commandline: apt install google-compute-engine
root@trac:~# journalctl |grep Instance\ ID
Aug 28 11:13:18 trac google_guest_agent[30286]: Instance ID changed, running first-boot actions
root@trac:~# ls -l /etc/ssh/ssh_host_ecdsa_key*
-rw------- 1 root root 227 Aug 28 11:13 /etc/ssh/ssh_host_ecdsa_key
-rw-r--r-- 1 root root 171 Aug 28 11:13 /etc/ssh/ssh_host_ecdsa_key.pub
I installed google-compute-engine after the OS upgrade because:
root@trac:~# apt-cache show google-compute-engine|grep Replace
Replaces: gce-cloud-config, gce-compute-image-packages (<< 20191115), gce-daemon, gce-startup-scripts
(Wasn't expecting a host key change though, my apologies)
Regards,
Jan