  $\beta$-Ga$_2$O$_3$-based semiconductor heterojunctions have recently
demonstrated improved performance at high voltages and elevated temperatures
and are thus promising for applications in power electronic devices and
harsh-environment sensors. However, the long-term reliability of these
ultra-wide band gap (UWBG) semiconductor devices remains barely addressed and
may be strongly influenced by chemical reactions at the p-n heterojunction
interface. Here, we experimentally demonstrate operation and evaluate the
reliability of Cr$_2$O$_3$:Mg/ $\beta$-Ga$_2$O$_3$ p-n heterojunction diodes at
during extended operation at 600$^\circ$C, as well as after 30 repeated cycles
between 25-550$^\circ$C. The calculated pO2-temperature phase stability diagram
of the Ga-Cr-O material system predicts that Ga$_2$O$_3$ and Cr$_2$O$_3$ should
remain thermodynamically stable in contact with each other over a wide range of
oxygen pressures and operating temperatures. The fabricated Cr$_2$O$_3$:Mg /
$\beta$-Ga$_2$O$_3$ p-n heterojunction diodes show room-temperature on/off
ratios >10$^4$ at $\pm$5V and a breakdown voltage (V$_{Br}$) of -390V. The
leakage current increases with increasing temperature up to 600$^\circ$C, which
is attributed to Poole-Frenkel emission with a trap barrier height of 0.19 eV.
Over the course of a 140-hour thermal soak at 600$^\circ$C, both the device
turn-on voltage and on-state resistance increase from 1.08V and 5.34
m$\Omega$-cm$^2$ to 1.59V and 7.1 m$\Omega$-cm$^2$ respectively. This increase
is attributed to the accumulation of Mg and MgO at the Cr$_2$O$_3$/Ga$_2$O$_3$
interface as observed from TOF-SIMS analysis. These findings inform future
design strategies of UWBG semiconductor devices for harsh environment operation
and underscore the need for further reliability assessments for
$\beta$-Ga$_2$O$_3$ based devices.
