Rather than setting StrictHostKeyChecking to no or using ssh_known_hosts in addons, I would prefer explicitly specifying the fingerprint. It seems that otherwise my deployment would be susceptible to man-in-the-middle attacks.
All the searches I did came up with folks recommending disabling security, which seems rather strange.
It turns out this is possible at least through creating a local known_hosts resource and using -o UserKnownHostsFile=known_hosts whenever using ssh or scp.
It would be good if https://docs.travis-ci.com/user/ssh-known-hosts/ pointed that out. Or provided syntax for including the public key.