None of the existing and upcoming Plug-and-Charge (PnC) related standards define privacy-preserving measures for protecting privacy-sensitive charging and billing data to prevent attacks such as the generation of movement profiles. To address this issue, we analyze PnC protocols with respect to privacy, identify requirements for privacy-preserving PnC solutions, and propose a PnC protocol extension enabling users to charge Electric Vehicle (EV) anonymously and service providers to securely bill their customers. Our approach addresses the complete PnC process chain and is based on a Direct Anonymous Attestation (DAA) protocol using a Trusted Platform Module (TPM) in the vehicle. Our analysis shows that our approach effectively protects the customers privacy while introducing only minimal additional protocol overhead.