The limited resources available for Smart Meter (SM) devices on large-scale Smart Grid (SG) networks impose several constraints on SMs authentication. Currently, available authentication schemes are not suitable for this type of network. In particular, factors such as power and memory consumption impact the protocol efficiency and the device lifetime. Furthermore, high computational complexity leads to scalability issues in real-world scenarios, wherein large SGs need to handle a huge number of requests coming at a high rate. In this paper, we propose a lightweight authentication protocol for Smart Grids (LAP-SG), a novel scheme accounting for real resource-constrained SM providing reduced computation power, memory requirements, communication overhead, and electricity consumption. We prove the security of LAP-SG using both informal security analysis and a formal security model. We further prove the security of LAP-SG by testing it using AVISPA and ProVerif tools, showing its security against all known attacks. To assess LAP-SG performance in a real-world scenario, we measure its performance using the configuration of the Atmel family of SM devices. When compared to the state of the art, LAP-SG attains three times Smaller computation cost, reduced communication costs (up to 400 bits), and nearly four times lower storage cost.