No. Typically the private key is generated in your browser and the certificate authority signs the public key in a cert request. There are other authentication schemes where a server keeps a private key and sends it to your email client when it is needed, but are not standard PKI.
If you decide to buy an email cert from verisign or someone else, they do not ever touch or see your private key.
DoD must do it differently than Verisign, because I know if I need one of my expired keys to open an old encrypted email, I can go recover it at a certain .mil site. I can see a list of all of the keys I have ever had at that site (back to 2003).
I have done it several times and I help people do it all the time.