We demonstrate an approach for improving the spectral linewidth of a spin torque nano-oscillator (STNO). Using He + ion irradiation, we tune the perpendicular magnetic anisotropy (PMA) of the STNO free layer such that its easy axis is gradually varied from strongly out-of-plane to moderate in-plane. As the PMA impacts the non-linearity N of the STNO, we can, in this way, control the threshold current, the current tunability of the frequency, and, in particular, the STNO linewidth, which dramatically improves by two orders of magnitude. Our results are in good agreement with the theory for nonlinear auto-oscillators, confirm theoretical predictions of the role of the nonlinearity, and demonstrate a straightforward path toward improving the microwave properties of STNOs.