Persistently high traffic loads and heterogeneous quality of service (QoS) requirements arising from machine-to-machine communication in wireless 5G systems require effective random access prioritization. 5G systems will likely evolve from mature wireless technologies, e.g., long term evolution (LTE). LTE conducts random access through preamble contention based on slotted Aloha principles. Prior studies have mainly examined random access prioritization for addressing temporary traffic bursts through manipulating the access contention procedure on a given set of preambles, such as adapting the number of permitted transmission attempts and back off windows. We conduct a detailed study of random access prioritization through separating (splitting) the random access preambles into non-overlapping priority classes. Based on the obtained insights, we develop the Load-Adaptive Throughput-MAximizing Preamble Allocation (LATMAPA). LATMAPA automatically adjusts the preamble allocation to the priority classes according to the random access load and a priority tuning parameter. Extensive analytical and simulation evaluations indicate that LATMAPA provides effective QoS differentiation across a wide range of random access loads, which are expected in 5G systems.