The formation of new shell gaps in intermediate mass neutron-rich nuclei are investigated within the relativistic Hartree-Fock-Bogoliubov theory and the role of the Lorentz pseudo-vector and tensor interactions is analyzed. Based on the Foldy-Wouthuysen transformation, we discuss in detail the role played by the different terms of the Lorentz pseudo-vector and tensor interactions in the formation of the $N=16$, 32 and 34 shell gaps. The nuclei $^{24}$O, $^{52,54}$Ca and $^{48}$Si are predicted with a large shell gap and zero ($^{24}$O, $^{52}$Ca) or almost zero ($^{54}$Ca, $^{48}$Si) pairing gap, making them candidates for new magic numbers in exotic nuclei. We found from our analysis that the Lorentz pseudo-vector and tensor interactions induce very specific evolutions of single-particle energies, which could clearly sign their presence and reveal the need for relativistic approaches with exchange interactions.