Low-loss, high frequency acoustic resonators cooled to millikelvin temperatures are a topic of great interest for application to hybrid quantum systems. When cooled to 20 mK, we show that resonant acoustic phonon modes in a Bulk Acoustic Wave (BAW) quartz resonator demonstrate exceptionally low loss (with $Q$-factors of order billions) at frequencies of 15.6 and 65.4 MHz, with a maximum $f.Q$ product of 7.8$\times10^{16}$ Hz. Given this result, we show that the $Q$-factor in such devices near the quantum ground state can be four orders of magnitude better than previously attained. Such resonators possess the low losses crucial for electromagnetic cooling to the phonon ground state, and the possibility of long coherence and interaction times of a few seconds, allowing multiple quantum gate operations.