Distance bounding protocols become more and more important because they are the most accurate solution to defeat relay attacks. They consist of two parties: a verifier and a prover. The prover shows that (s)he is close enough to the verifier. In some applications such as payment systems, using public-key distance bounding protocols is practical as no pre-shared secret is necessary between the payer and the payee. However, public-key cryptography requires much more computations than symmetric key cryptography. In this work, we focus on the efficiency problem in public-key distance bounding protocols and the formal security proofs of them. We construct two protocols (one without privacy, one with) which require fewer computations on the prover side compared to the existing protocols, while keeping the highest security level. Our construction is generic based on a key agreement model. It can be instantiated with only one resp. three elliptic curve computations for the prover side in the two protocols, respectively. We proved the security of our constructions formally and in detail.