The private key could be generated after the probe leaves Earth, via a process where many competing parties contribute seeding information.

Hence, barring deep compromises of the hardware, it will have never existed on Earth - only in the deep "Trusted Platform Module" (TPM) of the off-planet hardware.