Tienes el try-catch dentro del bucle. Mi propuesta.
Código PHP:
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numero;
String exit;
try {
do {
System.out.println("Introduce un numero: ");
numero = sc.nextInt();
System.out.println("¿Quieres cambiar de número (s/n)? : ");
exit = sc.next();
} while ( !"n".equalsIgnoreCase(exit) );
System.out.println("El cuadrado del numero " + numero + " es: " + Math.pow(numero, 2));
} catch (InputMismatchException ex) {
System.out.println("Formato de numero equivocado");
}
}
}