Does manually connecting to the server (from the same terminal as ansible is used) with SSH, removing the old host key fingerprint (a suitable command should be printed with the error message) and re-adding the new host key fingerprint (re-connect manually again and confirming saving the host key fingerprint) fix the issue?
Afterwards ansible should be able to connect without the error.
In the more distant past I also encountered a similar issue, where ansible updated the SSH host key algorithm, resulting in a different SSH host key and the same issues, see this discussion: