The issue is created by sssd.
Instead of re-installing freeipa, I did the below work-around:
Temporarily backup /var/lib/sss/pubconf /var/lib/sss/pubconf_bkp
ssh again to the remote machine. This will update the new hostkey.
Move back /var/lib/sss/pubconf_bkp to /var/lib/sss/pubconf
Now try again. The issue will not recur.
Note: Don't forget to move back /var/lib/sss/pubconf, else LDAP authentication will