While digital computers rely on software-generated pseudo-random number generators, hardware-based true random number generators (TRNGs), which employ the natural physics of the underlying hardware, provide true stochasticity, and power and area efficiency. Research into TRNGs has extensively relied on the unpredictability in phase transitions, but such phase transitions are difficult to control given their often abrupt and narrow parameter ranges (e.g., occurring in a small temperature window). Here we demonstrate a TRNG based on self-oscillations in LaCoO₃ that is electrically biased within its spin crossover regime. The LaCoO₃ TRNG passes all standard tests of true stochasticity and uses only half the number of components compared to prior TRNGs. Assisted by phase field modeling, we show how spin crossovers are fundamentally better in producing true stochasticity compared to traditional phase transitions. As a validation, by probabilistically solving the NP-hard max-cut problem in a memristor crossbar array using our TRNG as a source of the required stochasticity, we demonstrate solution quality exceeding that using software-generated randomness.