High-frequency gravity waves (HFGWs) observed by the Zhurong/Tianwen-1 and Perseverance/Mars 2020 rovers between 09:00 and 11:00 local time, from Ls 140° to 165° in Mars Year 36 was investigated. By analyzing the eccentricity of hodographs for monochromatic wind perturbations obtained from harmonic fittings, HFGWs were identified via their predominantly linear characteristics. The background atmosphere stability was estimated using the Richardson number from the Dynamic Meteorology Laboratory general circulation model simulation. We find that the frequency of HFGWs doubled following the onset of a regional dust storm (RDS) in the Utopia Planitia region, where the Zhurong rover landed. The propagation directions of the HFGWs were determined using their polarization relationships. The HFGWs observed by Zhurong predominantly propagated north-south direction before the RDS and then east-west after. The propagation direction changes were likely due to the atmospheric instability changes in the region before and after the storm.