Because our instances run in an autoscaling cluster, and we run multiple instances for high-availability, the IP addresses you connect to can be different each connection.
This causes ssh to report the IP address has been modified and requires you to update your known_hosts file to delete and re-add a new host key against a new IP address.
The problem can be resolved by using the SSH option CheckHostIP set to no:
sftp -o CheckHostIP=no 'serviceid\firstname.lastname@example.org'
This will ignore any IP future IP checks and resolve this issue.
Importantly - the IP address may change, but the host key fingerprint will never change:
2048 SHA256:vgxrsQY4LuABBPrAIdBHQSF+UQgF5PuWzsqtLYSAua4 email@example.com (RSA) 2048 MD5:f3:d6:0d:1d:a0:98:33:4f:b5:ef:f3:0d:e5:e5:e4:9f firstname.lastname@example.org (RSA)