My Galaxy Nexus was getting really slow over the last few weeks, meaning simple things like going to the homescreen took multiple seconds.
Turns out that the problem is the SD card filesystem / controller getting really slow once the SD card gets nearly filled up. You can verify this by running Androbench, a storage benchmark app. You should get a sequential write performance of a few MB/s (e.g. 8 MB/s), but when affected by the problem, you get about 0.x MB/s.
The fix is to delete files to make sure you have plenty of spare capacity, then run fstrim, neatly packaged in this app, followed by a reboot.
In case you haven’t rooted your phone for a while, the currently working way is using SuperSU, not Superuser.