The influence of a strain-induced uniaxial magnetoelastic anisotropy on the magnetic vortex core dynamics in microstructured magnetostrictive Co$_{40}$Fe$_{40}$B$_{20}$ elements was investigated with time-resolved scanning transmission x-ray microscopy. The measurements revealed a monotonically decreasing eigenfrequency of the vortex core gyration with the increasing magnetoelastic anisotropy, which follows closely the predictions from micromagnetic modeling.