Mobile operators offer a wide range of value-added services (VAS) to their subscribers (i.e., mobile users), which in turn generates around 15% of the telecommunication industry revenue. However, simultaneous VAS requests from a large number of mobile devices to a single server or a cluster in an internet-of-things (IoT) environment could result in an inefficient system, if these requests are handled one at a time as the present traditional cellular network scenario is. This will not only slow down the server's efficiency but also adversely impacts the performance of the network. The current (insecure) practice of transmitting user identity in plaintext also results in traceability. In this paper, we introduce the first known protocol designed to efficiently handle multiple VAS requests at one time, as well as ensuring the secure delivery of the services to a large number of requesting mobile users. The proposed batch verification protocol (BAS-VAS) is capable of authenticating multiple simultaneous requests received by a large number of mobile users. We demonstrate that the protocol preserves user privacy over the network. The provider's servers ensure the privacy of the requested service's priority by performing sorting over encrypted integer data. The simulation results also demonstrate that the proposed protocol is lightweight and efficient in terms of communication and computation overheads, protocol execution time, and batch and re-batch verification delay. Specifically, we perform batch and re-batch verification (after detecting and removing malicious requests from the batch) for multiple requests in order to improve the overall efficiency of the system, as well as discussing time, space and cost complexity analysis, along with the security proof of our protocol using Proverif.