Cita: En las pruebas que he realizado, mientras haya alguna referencia entre los registros
Precisamente eso es lo que se denomina "integridad referencial" y es el objetivo PRIMARIO de las FK. Evitar que puedas borrar, insertar o alterar algo sin respetar su dependencia.
Ponerlas en otra tabla NO ES EFICINENCIA, y por otro lado no afectará en nada, porque en esa tabla deberías definirlas como FK, con lo que vuelves a caer en la restricción.
No intentes inventar soluciones. Simplemente aprende a usar las FK según las reglas ya definidas, que son las que valen.
En cuanto a lo de bien puestas, es relativo. Si me atengo al modelo E-R, los ID son innecedsarios si ya tienes otros identificadores únicos, como son la columna NIVEL, que se supone que identifica a cada uno de los diferentes niveles.
Por otro lado, tu modelo de tres tablas sólo se justifica si un usuario dado puede tener N niveles de acceso diferentes, lo que sería irregular por decirlo suavemente. Diferentes niveles de acceso se suelen regular de otra forma.
Si un usuario solo tiene un único nivel, entonces la tabla usuarios_aux_nivel_acceso es superflua, y la FK del nivel debería estar en la tabla de usuario.