Authentication protocols are necessary for the receiver of a message to ascertain its origin in a distributed environment. Since they exchange cryptographic messages at the beginning of communication, their security is an essential requirement. However, most of the protocols have suffered from several kinds of attacks. A replay attack is one kind of those attacks. Attackers could launch it easily by replaying an eavesdropped message. Moreover, there are many types of replay attacks while most of the formal methods are not capable of detecting them. [3] classified various kinds of replay attacks and proposed a taxonomy. Therefore, it is necessary to verify authentication protocols deliberately with such a taxonomy for a basis. In this paper, at first, we give a clear definition and several remarks on replay attacks. Secondly we review the taxonomy of replay attacks presented in [3], and comment on its minor mistake. Finally we examine on the basis of the taxonomy the password-based authentication protocol, K1P, which was proposed in our earlier papers for protecting weak secrets efficiently. As a result of the examination, we have found that three way mutual K1P shown in [2] was vulnerable to one of replay attacks. Therefore, we improve three way K1P on security against the replay attack. Improved three way K1P is secure against replay attacks as well as guessing attacks and therefore it may be useful for security services of various communication networks.