Trust On First Use is exactly what I do. If I have to connect to a new machine, I identify it by its hostname, and send it my credentials (whatever credentials

Trust On First Use is exactly what I do. If I have to connect to a new machine, I identify it by its hostname, and send it my credentials (whatever credentials the owner just sent me in plaintext). If I get the warning and I'm pretty sure I connected to this machine before, I ask whoever owns the machine "hey did you do something weird with this machine? Like reimage it or rotate SSL certs or change the DNS entry so it's actually a different machine?" 99% of the time I'm not connecting to a machine for the first time, so (if I may be allowed some bad maths) this reduces my attack surface by a factor of 100. (If the owner didn't send me plaintext credentials but instead added my SSH key, I don't expose anything by using that, but I immediately follow up by doing other sensitive things like scp'ing code or credentials there).