Hi Jon,
I think our new host is more picky about what kind of keys it accepts. For one thing, the sshd on the new host is probably configured by default to accept only newer types of keys (this is recently updated Debian bookworm). And for another thing I believe a recent Gitlab update tightened up the requirements for keys, rendering e.g. older rsa keys invalid (I don't know that for a fact but I feel it's true).
If you could research a bit what types of keys are officially accepted by our setup, then perhaps that info could be included in a second Broadcast message for folks.
Dave