The surge of M2M devices imposes new challenges for the current cellular network architecture, especially in radio access networks. One of the key issues is that the M2M traffic, characterized by small data and massive connection requests, makes significant collisions and congestion during network access via the random access (RA) procedure. To resolve this problem, in this paper, we propose a paging cycle-based protocol to facilitate the random access procedure in LTE- A. The high-level idea of our design is to leverage a UE's paging cycle as a hint to preassign RA preambles so that UEs can avoid preamble collisions at the first place. Our rpHint has two modes: (1) collision-free paging, which completely prevents cross-collision between paged user equipment (UEs) and random access UEs, and (2) collision-avoidance paging, which alleviates cross-collision. Moreover, we formulate a mathematical model to derive the optimal paging ratio that maximizes the expected number of successful UEs. This analysis also allows us to adapt dynamically to the better one between the two modes. We show via extensive simulations that our design increases the number of successful UEs in an RA procedure by more than 3× as compared to the legacy RA scheme of the LTE.