Rare-earth hydrides can exhibit high-temperature superconductivity under high pressure. Here, we apply a crystal structure prediction method to the current record-holding $Tc$ material, LaH$\mathrm{<mrow\; data-mjx-texclass="ORD">10</mrow>}$, and a candidate for even higher $Tc$, YH$\mathrm{<mrow\; data-mjx-texclass="ORD">10</mrow>}$. We find a pressure-induced phase transition from the experimentally observed cubic LaH$\mathrm{<mrow\; data-mjx-texclass="ORD">10</mrow>}$ phase to a new hexagonal phase at around 420 GPa. This hexagonal phase could explain experimental observations of hcp impurities in fcc samples. We find that YH$\mathrm{<mrow\; data-mjx-texclass="ORD">10</mrow>}$ forms similar structures to LaH$\mathrm{<mrow\; data-mjx-texclass="ORD">10</mrow>}$ and discuss the sensitivity of superconductivity calculations to the computational parameters used.