The notion of authenticator, proposed by Bellare et al., is to transform a protocol secure in the authenticated-link model to a new one secure in the unauthenticated-link model. This notion admits a modular design and analysis of cryptographic protocols and thus greatly simplifies the underlying tasks. However, all previous authenticators are constructed via a so called MT-authenticator. This kind of authenticator authenticates each message independently. Thus, the round complexity of the resulting protocol is amplified by a multiplicative factor. In this paper, we propose two efficient authenticators which authenticate the protocol as a whole and the round complexity of the resulting protocol increases only by at most an additively small number. We also construct a very efficient key exchange protocol. Our protocol is provably secure under the general cryptographic assumption (especially without a concrete hardness assumption such as DDH or RSA). Of an independent interest, our security proof lies in the emulation based ideal-real model, instead of the widely adopted (seemingly weaker) SK-security. To our knowledge, this is the first protocol of its kind. It is worth mentioning that all our constructions are obtained by improving the related protocols of Bellare et al. [1].