In vibration fatigue analysis, spectral methods are used to evaluate the fatigue damage of structures experiencing random vibrations. Spectral methods fail under non-Gaussian and non-stationary loading conditions and various solutions have been proposed. Correction coefficients are promising and depend on the kurtosis and skewness of the system’s response, which requires extensive time-domain analyses. Performing time-domain analysis undermines the computational efficiency of spectral methods. The present manuscript proposes a modal decomposition-based approach to numerically efficiently compute the central moments required to obtain the kurtosis and skewness. The proposed method is numerically validated on a structure subjected to non-Gaussian random loads. The proposed method demonstrates results identical to the standard approach, showing a reduction in computation time of around two orders of magnitude. This extends the applicability of spectral methods in conjunction with correction coefficients for numerical estimation of fatigue damage in the frequency domain even in the case of non-Gaussian loadings.