Just to be clear mbreese is talking about if you have just set up a new server like a vps and when you first ssh/scp to the server you accept a compromised key such as through a MITM attack but as he said this is highly unlikely to occur.
Hopefully Linode doesn't have any internal gremlins.
Of course, the weak point there is SSL where the keys themselves are transmitted, but it did well to quell my paranoia.