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?