The Resource Public Key Infrastructure (RPKI) already protects around 50% of announced BGP prefixes, and around 28% of systems enforce RPKI validity in routing. RPKI binds ownership of prefixes to public keys inside certificates, which are signed by the respective issuer. For signatures and keys, RPKI currently exclusively supports RSA-2048, forbidding other algorithms and key sizes. In this work, we practically show that RPKI efficiency could significantly benefit from algorithm agility, allowing for smaller more efficient algorithms like Elliptic Curve Cryptography (ECC). We further illustrate that current plans for shifting algorithms, which will eventually become necessary to shift towards quantum-secure algorithms, are infeasible due to bandwidth limitations, validation overhead, and issues with patch management. From our observations, we derive a new agility procedure that uses separate repository versions additional to two separate trees (a mixed tree and a legacy tree) to enable incremental deployment of a new algorithm. In contrast to existing approaches, our procedure provides benefits also for early adopters, facilitating deployment.