En los bosques de alrededor de Ciudad Cohete tienes 90% de posibilidades de encontrar a Yuffie, en Junon es más difícil.
De todas formas como te han dicho, Wutai es opcional, el siguiente destino al que tienes que ir es volver a Gold Saucer, al museo que hay en el Battle Square concretamente (la pista te la da un herrero en una casa aislada al este de Gongaga, pero no hace falta que vayas).