"If you have a gut response to a story, you are not responding to something new ..you are really responding to a story you were told when you were six or seven…"
- Samuel R. Delany

If you think about it, this is a term that sounds better than it actually is if you look at the root words. The word "astrogate" is modeled on "navigate" - navigate literally means navi+gate or ship+drive (or lead). So a navigator is a driver of a ship. "Astrogate", on the other hand, is astro+gate or star+driver - I don't think they piloted any stars in this book.

It might make more sense from an Earth-bound perspective; as Methuselah's Children mentions, the space vessel New Frontiers looks like a star from the surface of the Earth. "Odd," commented Lazarus, "Orion seems to have added a fourth star to his belt."

As far as dates are concerned, there is a slight problem, which is that two versions of this story were published. The earlier, shorter version was published in 1941; since I've been using the 1958 version I've given the date you see above. This term probably appears in the earlier version, but I have no way to check. Anyone? The first use of the basic word "astrogation" was probably Lasser's Conquest of Space, from 1931.

The word "astrogating" appears in The Venus Germ published in Wonder Stories in 1932 by R.F. Starzl and F. Pragnell:

Haye breathed easier. The very fact that he was still alive proved that the astrogating officers had the situation in hand.

See also the term astrographer from The Mystery of the Twilight Belt (1934) by JNT Lintott.

Thanks to an anonymous reader who wrote in asking for clarification.