We use first-principles total-energy calculations based on density functional theory to study the site occupancy and magnetic properties of Al-substituted $M$-type strontium hexaferrite SrFe$_{12-x}$Al$_{x}$O$_{19}$ with $x=0.5$ and $x=1.0$. We find that the non-magnetic Al$^{3+}$ ions preferentially replace Fe$^{3+}$ ions at two of the majority spin sites, $2a$ and $12k$, eliminating their positive contribution to the total magnetization causing the saturation magnetization $M_s$ to be reduced as Al concentration $x$ is increased. Our formation probability analysis further provides the explanation for increased magnetic anisotropy field when the fraction of Al is increased. Although Al$^{3+}$ ions preferentially occupy the $2a$ sites at a low temperature, the occupation probability of the $12k$ site increases with the rise of the temperature. At a typical annealing temperature ($> 700,^{circ}{rm C}$) Al$^{3+}$ ions are much more likely to occupy the $12k$ site than the $2a$ site. Although this causes the magnetocrystalline anisotropy $K_1$ to be reduced slightly, the reduction in $M_s$ is much more significant. Their combined effect causes the anisotropy field $H_a$ to increase as the fraction of Al is increased, consistent with recent experimental measurements.