The recent discovery of n-type Mg$_3$Sb$_2$ thermoelectric has ignited intensive research activities on searching for potential n-type dopants for this material. Using first-principles defect calculations, here we conduct a systematic computational screening of potential efficient n-type lanthanide dopants for Mg$_3$Sb$_2$. In addition to La, Ce, Pr, and Tm, we find that high electron concentration ($geq$ 10$^{20}$ cm$^{-3}$ at the growth temperature of 900 K) can be achieved by doping on the Mg sites with Nd, Gd, Ho, and Lu, which are generally more efficient than other lanthanide dopants and the anion-site dopant Te. Experimentally, we confirm Nd and Tm as effective n-type dopants for Mg$_3$Sb$_2$ since doping with Nd and Tm shows superior thermoelectric figure of merit zT $geq$ 1.3 with higher electron concentration than doping with Te. Through codoping with Nd (Tm) and Te, simultaneous power factor improvement and thermal conductivity reduction are achieved. As a result, we obtain high zT values of about 1.65 and 1.75 at 775 K in n-type Mg$_{3.5}$Nd$_{0.04}$Sb$_{1.97}$Te$_{0.03}$ and Mg$_{3.5}$Tm$_{0.03}$Sb$_{1.97}$Te$_{0.03}$, respectively, which are among the highest values for n-type Mg$_3$Sb$_2$ without alloying with Mg$_3$Bi$_2$. This work sheds light on exploring promising n-type dopants for the design of Mg$_3$Sb$_2$ thermoelectrics.