This is my implementation using the recursive identity for f_{2n+1} and f_{2n}. It's faster than ofibs on my machine, but I think it still has linear time growth.
(define (square n) $ * n n)
(define (fibs n)
$ cond ((= n 0) 0)
((= n 1) 1)
((= n 2) 1)
((even? n)
$ let ($ n2 $ / n 2)
$ - (square $ fibs $ + n2 1) $ square $ fibs $ - n2 1)
$ else
$ let ($ n2 $ / (- n 1) 2)
$ + (square $ fibs n2) $ square $ fibs $ + n2 1)
(define (ofibs n)
$ if (= n 0)
0
$ let loop ((i 1) (a 0) $ b 1)
$ if (= i n)
b
$ loop (+ i 1) b $ + a b)