This paper proposes a relative navigation framework using flash LiDAR aided-inertial navigation and surfel grid maps for in-situ autonomous exploration of small solar system bodies' (SSSB) surfaces. The key idea of the relative navigation is division of an entire flight area into several sub-areas, in each of which local navigation estimates and a local map are created in a node frame representing local frame in that sub-area. By changing the node frame in different sub-areas, estimation error and mapping error are bounded and do not accumulate. Varying local gravity vector on the SSSB surface is taken into account when a new node frame is defined. Our flash LiDAR pre-processing applies a scan-to-map matching algorithm and provides direct observation of spacecraft's position and attitude in the node frame to an error state Kalman filter. The surfel grid map representing local terrestrial environment around the spacecraft permits efficient scan-to-map matching and straightforward analysis on the SSSB surface. Simulation tests in a specialized high fidelity simulated SSSB environment present results of validation and performance evaluation of our relative navigation solution and show the viability of this novel navigation solution.