When you try to ssh into a instance and it failed giving errors which says remote host identification changed, possibly you have tried to ssh into that earlier but either it's been mapped to a IP or dns name has been assigned to that instance.you can resolve this issue ..