В семье адмирала Рассохо не было моряков. Его отец Иван Петрович Рассохо, украинец из села Перервенец Полтавской губернии, во время Русско-японской войны воевал в Манчжурии рядовым казаком в казачьем корпусе генерала Мищенко. Он заслужил два «Георгия», но в боях под Ляояном был тяжело ранен и оказался в японском плену. После войны Ивана Рассохо направили в лагерь для бывших военнопленных в Пензу, где уже после освобождения он женился на 17-летней работнице бумажной фабрики Груне Глазковой.
В семье Ивана и Агриппины Рассохо со временем появилось 11 детей. Родители будущего адмирала прожили в Пензе всю жизнь.
Анатолий родился б декабря (23 ноября) 1914 г. Когда ему было пять лет, он впервые увидел нескольких балтийских моряков (одним из них оказался легендарный матрос-революционер Николай Маркин). Они произвели сильное впечатление на Толю, и он уже тогда решил: буду моряком.