See my reply here:
You’ll need to delete the known_hosts entry each time you reprovision the server.
known_hosts