Clearance probably. It's really not a big deal with the index in place and it gives you more flexibility for revoking access to specific users without blowing out everyone's cookie. In practice, it's not a big deal performance wise. In a system where it would matter, you'd probably be past the point of an off-the-shelf gem being a good solve.
The only way I see this as a Rails problem is that Rails makes it easy to get saddled with lots of external dependencies. Otherwise, it's a problem with how external dependencies are managed.
If it's not the number and quality of dependencies then it's the wrong type. I usually stay away from gems that provide syntactic sugar or provide an alternative to ruby / rails defaults. If I'm using 5% of some library, I'd rather write it myself and only address the 5% that I need. If it's not maintained, I stay away. Etc.
A little discipline on what gems get included would go a long way to solving the perceived problems. Gems are generally designed to solve a much more generic version of the problem you're trying to solve and maybe not even the exact same problem, if you're messing with the innards too much, that gem is probably not a good enough fit.
Less is always better when it comes to dependencies.
The nice thing is that browsers provide good control for managing one's cookies, and browsers like Safari ship with pretty sensible, user-friendly defaults (block cookies from 3rd party sites).
The current privacy Valdez is flash cookies, which are shockingly ubiquitous. You can't clear them easily (clearing browser cookies won't work) and they bypass browser cookie defaults. I polled a lot of developers and just about every single one of them had no idea about them -- and if that demographic is oblivious to them, imagine the rest of the population.