Due to lack of spacecraft's global position and attitude information on small solar system bodies (SSSBs) like asteroids, only relative state measurements are available for navigation. Therefore, relative navigation with respect to a local reference frame is the basis for in-situ autonomous exploration on the asteroids. The relative navigation changes a local reference frame during the flight, which guarantees local accuracy of state estimation and mapping. We present the relative navigation framework using surfel grid map-based scan-to-map matching for localization and mapping on asteroid surface. We also propose a terrain-based path planning that makes use of inherent terrain surface properties of surfel grid maps. A thorough validation of our navigation approach and comparison to a global flash LiDAR-based navigation in different flight scenarios and in both MIL (model-in-the-loop) and real-time PIL (processor-in-the-loop) tests show the viability of this novel navigation framework.