The growing penetration of converter-Interfaced Generators (CIG) in electricity grids has diminished inertia levels. Micro-Grids (MGs), with their high penetration of CIGs, are particularly vulnerable to the reduced inertia levels presenting a challenge to their secure and reliable operation. MG system planning must now incorporate the analysis of dynamic system security complementing traditional resource adequacy assessments. However, integrating transient security constraints into MG planning is complex due to the non-convex and non-linear nature of the analytical expressions for frequency metrics and power flow constraints. To address this challenge, this paper presents a decomposition-based approach to the MG investment planning problem that leverages dual solutions to derive dual-cutting planes, effectively constraining the feasible solution space. This enhances computational tractability and optimality by ensuring that the sensitivity of decisions at each stage can be accurately captured. This facilitates the identification of cost-effective investment strategies that balance economic objectives and security requirements, optimizing the placement of inertia services and accelerating algorithm convergence. The significance of the proposed algorithms is validated on a low- and medium-voltage network under various operating scenarios and security levels. Results demonstrate that the proposed algorithms yield solutions that are more sensitive to frequency support needs and converge more rapidly.