Traditional DNS Security Extensions (DNSSEC) face challenges in highly dynamic and geo-distributed environments, particularly concerning the size of authenticated responses and the lack of inherent long-term auditability. While DNSSEC provides cryptographic authentication for DNS records, its reliance on transmitting all contributing resource records (RRs) for signature validation leads to inefficient data transfer and increased operational complexity. We propose a novel approach that enhances DNSSEC’s capabilities without altering its fundamental authentication mechanism, focusing on efficiency and verifiable data integrity. Our solution introduces a new DNS record type, Authenticated Proof of Existence (APEX), which leverages Verifiable Data Structures (VDS)–such as Merkle Trees–to provide concise, cryptographic proofs for individual DNS records. This method significantly reduces response sizes, improves authentication efficiency, and enables long-term auditable logs of DNS information through third-party verifiable storage. By extending DNS’s role in key management and service authentication, particularly in large-scale scenarios like IoT, APEX offers a scalable, secure, and auditable foundation for postquantum cryptography advent.