Emerging resource-constrained cellular Internet of Things (IoT) applications such as drone swarms, autonomous vehicles, and remote surgery via mixed reality demand millisecond-level time synchronization. Narrow-Band IoT (NB-IoT), the leading low-power wide-area technology, struggles to meet these requirements. The root cause lies in the non-deterministic delays inherent in the 5G protocol design. Uplink reliability and scheduling mechanisms introduce asymmetric latencies that disrupt conventional time synchronization algorithms such as the Network Time Protocol (NTP). Time-critical packets are further affected by deep-sleep wake-up latency, base station scheduling delays, uplink/downlink asymmetry, and unpredictable drift from inexpensive oscillators. Together, these factors can accumulate into timing errors on the order of hundreds of milliseconds. In this paper, we first quantify timing errors across five dimensions on a commercial NB-IoT network. We then present SynchroNB, an on-device framework that combines lightweight machine learning with a cross-layer control loop. SynchroNB forecasts 5G network volatility and crystal drift to adaptively wake the cellular modem, reserves uplink resources just in time, switches into resilience mode when the wireless link degrades, and prioritizes time synchronization packets in the MAC-layer queue. We deploy SynchroNB on commercial NB-IoT hardware and evaluate it over a live 5G network. Our experiments show that SynchroNB achieves single-millisecond-level synchronization accuracy under NB-IoT uplink/downlink asymmetry and, diverse wireless conditions, while requiring only \(36\%\) of the radio-on time and \(25\%\) of the bandwidth of the NTP baseline, transforming NB-IoT time synchronization from a reactive protocol into an intelligent, self-tuning control loop.