Satellite communication is easily exposed to attacks like eavesdropping of information, abnormal sending of packet, reusing of message, forgery/alteration of data etc. To prevent these attacks, Key Exchange protocol is conducted between NCC (Network Control Centre) and RCST (Return Channel Satellite Terminal). ETSI (European Telecommunication Standards Institute) designed a Main Key Exchange protocol exchanging keys through cookie-based user authentication. Exposure of data at the early time when NCC and RCST exchange cookies, however, brings Man-in-the-middle attack. Replay attack is also possible because it doesn't make any encryption during data transmission. Though Certificate-based protocol was suggested to prevent Man-in-the-middle attack, it is not appropriate for satellite environment. This paper suggests the protocol which can prevent Man-in-the-middle attack using Timestamp, and compare the proposed protocol with existing protocols through performance analysis, showing its resource management and the efficiency of communication. The procedure of preventing Man-in-the-middle attack of the suggested protocol is examined through safety analysis, and it can prevent Replay attack with addition of ID parameter.