The quasi two-dimensional Mott insulator $alpha$-RuCl$_3$ is proximate to the sought-after Kitaev quantum spin liquid (QSL). In a layer of $alpha$-RuCl$_3$ on graphene the dominant Kitaev exchange is further enhanced by strain. Recently, quantum oscillation (QO) measurements of such $alpha$-RuCl$_3$ / graphene heterostructures showed an anomalous temperature dependence beyond the standard Lifshitz-Kosevich (LK) description. Here, we develop a theory of anomalous QO in an effective Kitaev-Kondo lattice model in which the itinerant electrons of the graphene layer interact with the correlated magnetic layer via spin interactions. At low temperatures a heavy Fermi liquid emerges such that the neutral Majorana fermion excitations of the Kitaev QSL acquire charge by hybridising with the graphene Dirac band. Using ab-initio calculations to determine the parameters of our low energy model we provide a microscopic theory of anomalous QOs with a non-LK temperature dependence consistent with our measurements. We show how remnants of fractionalized spin excitations can give rise to characteristic signatures in QO experiments.