Quantum interference between time-reversed electron paths in two dimensions leads to the well-known weak localization correction to resistance. If spin-orbit coupling is present, the resistance correction is negative, termed weak anti-localization (WAL). Here we report the observation of WAL coexisting with exchange coupling between itinerant electrons and localized magnetic moments. We use low-temperature magneto-transport measurements to investigate the quasi-two-dimensional, high-electron-density interface formed between SrTiO$_3$ (STO) and the anti-ferromagnetic Mott insulator NdTiO$_3$ (NTO). As the magnetic field angle is gradually tilted away from the sample normal, the data reveals the interplay between strong $k$-cubic Rashba-type spin-orbit coupling and a substantial magnetic exchange interaction from local magnetic regions. The resulting quantum corrections to the conduction are in excellent agreement with existing models and allow sensitive determination of the small magnetic moments (22 $mu_B$ on average), their magnetic anisotropy and mutual coupling strength. This effect is expected to arise in other 2D magnetic materials systems.