Holy Hell, I hope you mistyped something!
It is 2015. If you've got a single password (your private key) with root access to that many machines, something is terribly wrong over at Debian.
Others have replied, but I think I should do so as well: Yes, we don't use a PGP key to log in to thousands of machines, but we use it to validate package uploads that enter the archive. If I sign+upload a malicious binary package, it's just a matter of time until it reaches users.
Of course, there are some caveats: First, I must convince users to use my package. This is, my malicious code should not go in a very uninteresting package, it would go to one that I know that has many users. But, second, it should not attract too much attention, as others would likely find my backdoor. Say, if I wanted to reach maximum number of machines, I could update an "Essential" package, such as base-files. But first, the package is not mine (so my friend Santiago, the package maintainer, would jump at the unexpected upload). And it does not get updates often, so others would probably debdiff it and uncover my betrayal. And third, that would make my malicious package enter the unstable distribution. Were I looking for a real foothold on a large amount of computers, I'd have to wait probably around two years until it reaches a stable release.
That's why I said "thousands" and not "millions" :-)