The last-level cache is vulnerable to cross-core conflict-based attacks as the cache is shared among multiple cores. A fully associative last-level cache with a random replacement policy can mitigate these attacks. However, it is impractical to design a large last-level cache that is fully associative. One of the recent works, named Mirage, provides an illusion of a fully associative cache with a decoupled tag and data store and a random replacement policy. However, it incurs a storage overhead of $20 \%$, static power overhead of $18.16 \%$, and area overhead of $6.86 \%$ compared to a non-secure baseline cache of 16MB. One of the primary contributors to the additional storage requirements is the usage of extra invalid tag entries that are used in a skewed way without changing the number of data store entries. These invalid tag entries provide a strong security guarantee. We observe that more than $80 \%$ of last-level cache’s data store entries are dead on arrival, providing negligible utility in terms of performance improvement as they do not get reused in their lifetimes. Also, in general, the data store entries occupy $\approx$ eight times more storage than tag store entries. Based on these observations, we propose Maya, a storage efficient and yet secure last-level randomized cache that compensates for the additional storage of tag store entries by using fewer data store entries. Maya increases the tag store entries for security and reuse detection and uses fewer data store entries that only store the reused data. Our proposal provides a strong security guarantee, which is one set-associative eviction in $10^{32}$ line fills at the last-level cache. This is equivalent to a line installed once in $10^{16}$ years to mount an eviction attack. Maya provides this security guarantee with a 12 MB data store that occupies $28.11 \%$ less area and $5.46 \%$ less static power when compared to a non-secure baseline of 16 MB cache.