Random access channel (RACH) procedure is critical to support a multitude of devices transmitting small data payloads while ensuring low-latency access. In 3GPP Release 16, a two-step RACH is proposed to alleviate signaling overhead and access latency. While benefits are noticeable, collisions still persist. In this paper, we propose a novel non-orthogonal multiple access (NOMA)-enhanced 2-step RACH scheme (NOMA-RACH) that jointly leverages the benefits of access class barring (ACB), 2-step RACH, and NOMA random access (NOMA-RA) to further enhance the performance. We conduct a holistic study that accounts for entire access latency. The scheme optimizes NOMA access probabilities, utilizes an adjustable barring mechanism for delay-sensitive devices, and identifies the optimal barring rate for low latency. We develop a Markov chain model to analyze NOMA access and derive the optimal access probabilities and throughput of NOMA blocks. To cope with the practical scenarios with constantly changing user equipment (UE) traffic, we propose a deep contextual multi-armed bandit (DCMAB) model that optimizes the NOMA throughput and dynamically adjusts the barring rate based on the observable channel feedback. Our simulation results demonstrate that the DCMAB model performs better than benchmark schemes and remains close to the optimal latency confirming the effectiveness of our proposed scheme under changing UE traffic.