The record age ${\tau }_k$, defined as the time between the $k$th and $(k+1)$st record-breaking events, is a central observable of extreme-value statistics. In translation-invariant Markovian processes, the absence of memory renders record ages independent and identically distributed. How memory induces aging –a dependence of ${\tau }_k$ on $k$– and correlations between record ages remain fundamental questions closely connected to widely observed aging phenomena in non-Markovian dynamics. In this Letter, we focus on saturating self-interacting random walks, a broad class of non-Markovian processes. We derive the exact asymptotic distribution of the record age ${\tau }_k$, which provides a rare microscopic derivation of recent scaling predictions. We go further and determine its joint statistics with a future record age ${\tau }_l$, $l>k$. We show that record ages can be strongly correlated: an earlier anomalously long record age can enhance or suppress the probability of a subsequent long record age by an order of magnitude.