A private key with multiple public keys?
Here's an idea:


Alice's private key is an AES key $k$, which Alice picks randomly.  Yes, we're using an AES key as a private key; bear with me a moment...
To generate a new public key, Alice picks a random value $r$, and generates the pair $(\text{AES}_k(r), rG)$, which she publishes, and which I will refer to as $(b, H)$.  Alice can optionally forget the value $r$ she picked.  Alice can generate and publish as many public keys as she needs...
To encrypt a message $m$ with this public key $(b, H)$, Bob selects a random value $s$, computes the point $sG$ and the AES key $KDF(sH)$, and outputs the triplet $(b, sG, \text{AES}_{KDF(sH)}(m))$
To decrypt $(b, sG, \text{AES}_{KDF(sH)}(m))$, Alice first decrypts $\text{AES}_k^{-1}(b) = r$, (and if that decryption fails, the message wasn't meant for her).  Then she computes $r(sG) = s(rG) = sH$, computes $KDF(sH)$, and then decrypts $\text{AES}_{KDF(sH)}(m))$, giving her the message $m$.


Two different public keys from Alice are unlinkable, as the only connection is that they contain the encryption of two different values with the same AES key, and that's indistinguishable from random.

And, all operations take time independent of the number of public keys Alice generates...

(Note: you'll use some authenticating encryption mode of AES, such as AES-GCM...)