Sometimes when trying to start my wifes 95 5.0 f150 it makes this strange noise when turning over but finally starts. Other times starts right up. Have replaced starter recently,but still the same.What should I check?

 

Check the Teeth on the Flywheel and see if any of them are "rounded off" on the corners as if the starter has ground on them. There may be a spot in the flywheel where the teeth are messed up so as not to grab the flywheel to turn the motor over.