Kerberos is designed to provide strong authentication between client and application servers which are working in distributed network environment by using symmetric-key cryptography, and supposed to trust other systems of the realm. In this paper, we design an efficient and strong authentication mechanism by introducing the public/private-key to Kerberos. In the mechanism to make a system more secure, the value of the session key is changed everytime using MAC(message authentication code) algorithm with the long-term key for user-authentication and a random number exchanged through the public key. Also, we employ a mutual authentication method, which is used on challenge-response mechanism based on digital signatures, to improve trust between realms, and present a way of reducing the number of keys by simplifying authentication steps.