In order to test recently predicted ballistic nanofriction (ultra-low drag and enhanced lubricity) of gold nanocrystals on graphite at high surface speeds, we use the quartz microbalance technique to measure the impact of deposition of gold nanocrystals on graphene. We analyze our measurements of changes in frequency and dissipation induced by nanocrystals using a framework developed for friction of adatoms on various surfaces. We find the lubricity of gold nanocrystals on graphene to be even higher than that predicted for the ballistic nanofriction, confirming the enhanced lubricity predicted at high surface speeds. Our complementary molecular dynamics simulations indicate that such high lubricity is due to the interaction strength between gold nanocrystals and graphene being lower than previously assumed for gold nanocrystals and graphite.