The paper addresses the challenge of timing advance (TA) estimation in low earth orbit (LEO) satellite networks, where the existing 5G TA estimation mechanisms are not directly applicable due to the fast satellite movement and large beam footprint size. The proposed enhanced TA estimation approach includes a user-side time-frequency pre-compensation method and an improved preamble format design. The pre-compensation method leverages frequency offset measurements from synchronization signal blocks (SSBs) broadcasted by satellites during the initial cell search phase. For the random access phase, the upper bound of inter-preamble interference is derived for a preamble format advised by 3GPP, and it is shown that the interference level is closely related to the square of the number of partial-period cross-correlation operations. Inspired by this result, a cyclic prefix-free preamble format is designed, featuring extended guard time, differential power allocation, and flexible preamble structure. Numerical results demonstrate that the proposed approach reduces the missed detection rate of preambles within a beam to less than 1% for 32, 48, and 64 users at an SNR of -6 dB, and limits the TA estimation error of detected users to 25 time-domain sampling points when the subcarrier spacing is 30 kHz and the operation frequency is 27 GHz.The paper addresses the challenge of timing advance (TA) estimation in low earth orbit (LEO) satellite networks, where the existing 5G TA estimation mechanisms are not directly applicable due to the fast satellite movement and large beam footprint size. The proposed enhanced TA estimation approach includes a user-side time-frequency pre-compensation method and an improved preamble format design. The pre-compensation method leverages frequency offset measurements from synchronization signal blocks (SSBs) broadcasted by satellites during the initial cell search phase. For the random access phase, the upper bound of inter-preamble interference is derived for a preamble format advised by 3GPP, and it is shown that the interference level is closely related to the square of the number of partial-period cross-correlation operations. Inspired by this result, a cyclic prefix-free preamble format is designed, featuring extended guard time, differential power allocation, and flexible preamble structure. Numerical results demonstrate that the proposed approach reduces the missed detection rate of preambles within a beam to less than 1% for 32, 48, and 64 users at an SNR of -6 dB, and limits the TA estimation error of detected users to 25 time-domain sampling points when the subcarrier spacing is 30 kHz and the operation frequency is 27 GHz.