The mobile cloud computing (MCC) has enriched the quality of services that the clients access from remote cloud-based servers. The growth in the number of wireless users for MCC has further augmented the requirement for a robust and efficient authenticated key agreement mechanism. Formerly, the users would access cloud services from various cloud-based service providers and authenticate one another only after communicating with the trusted third party (TTP). This requirement for the clients to access the TTP during each mutual authentication session, in earlier schemes, contributes to the redundant latency overheads for the protocol. Recently, Tsai et al have presented a bilinear pairing based multi-server authentication (MSA) protocol, to bypass the TTP, at least during mutual authentication. The scheme construction works fine, as far as the elimination of TTP involvement for authentication has been concerned. However, Tsai et al scheme has been found vulnerable to server spoofing attack and desynchronization attack, and lacks smart card-based user verification, which renders the protocol inapt for practical implementation in different access networks. Hence, we have proposed an improved model designed with bilinear pairing operations, countering the identified threats as posed to Tsai scheme. Additionally, the proposed scheme is backed up by performance evaluation and formal security analysis.