Repo cleanup problem

I'm sorry, if it is a FAQ.

I use git to track my own changes in a project, i.e, this is a private (not public) repository. Some time ago I've accidentally committed a big amount (about of 50M) of crap into the repository, and make a mature set of commits after this.

For now I'm looking for a way to remove the garbage commit. I've found a way to remove any commit using git-checkout, git-reset and git-rebase. But, when I even git-reset the repository to the very first (root) commit, I see the size is still large enough, i.e., the crap is still there. I've tried many combinations of git-gc, git-prune, git-repack, git-prune-packed etc, but the size of the repository is still the same. The only way I see now is to git-clone the repository -- the new one is essentially smaller, but needs to reconstruct the local branches.

Is this (make a clone) the only proper way to clenup a repository, or there is another magic tool to cleanup the repositories?