It's explained in Men in Black 3 that the Boglodite homeworld is 20 years away.  This means that after Boris killed K he travels to his home world.  After inciting his people to attack Earth he has them travel back and attack Earth.  In total it takes Boris 20 years to get home and another 20 years to get back to Earth with the Boglodite army so that explains the 40ish gap in years.

http://lgm.cl/tvtropes/Film/MenInBlack2.html

> The reason why the invasion didn't occur sometime in 1969 instead of
> the morning of the change despite being mentioned repeatedly that the
> race is extinct for 40 years because when J goes back in time and asks
> O about K, he is told that Boris escapes to his planet 20 light-years
> away. So it took a 40 year round-trip to go back to his planet and
> come back to invade with an army.