Since many GSM network operators have roaming agreements with foreign operators, users can often continue to use their mobile phones when they travel to other countries. There are several drawbacks found in existing authentication protocols of GSM, such as the fact that VLR cannot be authenticated, unbalanced communication bandwidth consumption between VLR and HLR, and storage overhead in VLR. Recently, many authentication protocols have been proposed to solve those drawbacks of the existing GSM authentication protocols, but they cannot alleviate all drawbacks without altering the GSM architecture. In this paper, we propose a novel mutual authentication protocol to solve all of the above problems without changing the existing GSM architecture.